Problem: For a given set of two-dimensional points S, let's denote its extension E(S) as the result of the following algorithm:

Create another set of two-dimensional points R, which is initially equal to S. Then, while there exist four numbers x_1, y_1, x_2 and y_2 such that (x_1, y_1) ∈ R, (x_1, y_2) ∈ R, (x_2, y_1) ∈ R and (x_2, y_2) ∉ R, add (x_2, y_2) to R. When it is impossible to find such four integers, let R be the result of the algorithm.

Now for the problem itself. You are given a set of two-dimensional points S, which is initially empty. You have to process two types of queries: add some point to S, or remove some point from it. After each query you have to compute the size of E(S).

Input

The first line contains one integer q (1 ≤ q ≤ 3 ⋅ 10^5) — the number of queries.

Then q lines follow, each containing two integers x_i, y_i (1 ≤ x_i, y_i ≤ 3 ⋅ 10^5), denoting i-th query as follows: if (x_i, y_i) ∈ S, erase it from S, otherwise insert (x_i, y_i) into S.

Output

Print q integers. i-th integer should be equal to the size of E(S) after processing first i queries.

Example

Input


7
1 1
1 2
2 1
2 2
1 2
1 3
2 1


Output


1 2 4 4 4 6 3 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
mt19937 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
const long double PI = 3.141592653589793;
const long long INF = 9223372036854775807ll;
const long long mod = 1e9 + 7;
const long long N = 6e5 + 2;
struct state {
  long long u, sz_u, v, sz_v, xu, yu, xv, yv;
  state(long long u, long long sz_u, long long v, long long sz_v, long long xu,
        long long yu, long long xv, long long yv)
      : u(u), sz_u(u), v(v), sz_v(sz_v), xu(xu), yu(yu), xv(xv), yv(yv) {}
};
struct dsu_rollback {
  vector<long long> id, sz, x, y;
  long long components;
  long long ans;
  stack<state> save;
  dsu_rollback() {}
  dsu_rollback(long long n) {
    id.resize(n), sz.resize(n);
    x.resize(n), y.resize(n);
    for (long long i = 0; i < n; ++i) {
      sz[i] = 0;
      id[i] = i;
      if (i <= 3e5) {
        x[i] = 1;
        y[i] = 0;
      } else {
        y[i] = 1;
        x[i] = 0;
      }
    }
    components = n;
    ans = 0;
  }
  long long root(long long u) {
    while (u != id[u]) u = id[u];
    return u;
  }
  bool merge(long long u, long long v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    components--;
    if (sz[v] > sz[u]) {
      swap(u, v);
    }
    save.push(state(u, sz[u], v, sz[v], x[u], y[u], x[v], y[v]));
    id[v] = u;
    sz[v] = 0;
    sz[u] += sz[v];
    ans -= x[u] * y[u] + x[v] * y[v];
    x[u] += x[v];
    y[u] += y[v];
    ans += x[u] * y[u];
    x[v] = 0;
    y[v] = 0;
    return true;
  }
  void rollback() {
    if (save.empty()) return;
    state now = save.top();
    save.pop();
    components++;
    ans -= x[now.u] * y[now.u];
    id[now.u] = now.u;
    id[now.v] = now.v;
    sz[now.u] = now.sz_u;
    sz[now.v] = now.sz_v;
    x[now.u] = now.xu;
    y[now.u] = now.yu;
    x[now.v] = now.xv;
    y[now.v] = now.yv;
    ans += now.xu * now.yu + now.xv * now.yv;
  }
};
struct query {
  long long u, v;
  bool united;
  query() {}
  query(long long u, long long v) : u(u), v(v) {}
};
struct QueryTree {
  vector<vector<query>> t;
  dsu_rollback dsu;
  long long T;
  QueryTree(long long T, long long n) : T(T) {
    dsu = dsu_rollback(n);
    t.resize(4 * T + 4);
  }
  void add_to_tree(long long v, long long l, long long r, long long ul,
                   long long ur, query& q) {
    if (ul > ur) return;
    if (l == ul && r == ur) {
      t[v].push_back(q);
      return;
    }
    long long mid = (l + r) / 2;
    add_to_tree(2 * v, l, mid, ul, min(ur, mid), q);
    add_to_tree(2 * v + 1, mid + 1, r, max(ul, mid + 1), ur, q);
  }
  void add_query(query q, long long l, long long r) {
    add_to_tree(1, 0, T - 1, l, r, q);
  }
  void dfs(long long v, long long l, long long r, vector<long long>& ans) {
    for (query& q : t[v]) {
      q.united = dsu.merge(q.v, q.u);
    }
    if (l == r)
      ans[l] = dsu.ans;
    else {
      long long mid = (l + r) / 2;
      dfs(2 * v, l, mid, ans);
      dfs(2 * v + 1, mid + 1, r, ans);
    }
    for (query q : t[v]) {
      if (q.united) dsu.rollback();
    }
  }
  vector<long long> solve() {
    vector<long long> ans(T);
    dfs(1, 0, T - 1, ans);
    return ans;
  }
};
void solve() {
  long long q;
  cin >> q;
  map<pair<long long, long long>, long long> connect;
  QueryTree qt(q + 1, 6e5 + 2);
  for (long long i = 0; i < q; ++i) {
    long long a, b;
    cin >> a >> b;
    b += 3e5;
    if (connect.find({a, b}) != connect.end()) {
      query f(a, b);
      qt.add_query(f, connect[{a, b}], i - 1);
      connect.erase({a, b});
    } else
      connect[{a, b}] = i;
  }
  for (auto left : connect) {
    query f(left.first.first, left.first.second);
    qt.add_query(f, left.second, q);
  }
  vector<long long> pr = qt.solve();
  for (long long i = 0; i < q; ++i) {
    cout << pr[i] << " ";
  }
  cout << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  solve();
  return 0;
}