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;
inline long long read() {
  long long f = 1, x = 0;
  char s = getchar();
  while (s < '0' || s > '9') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s >= '0' && s <= '9') {
    x = x * 10 - '0' + s;
    s = getchar();
  }
  return x * f;
}
inline long long qkmul(long long x, long long y, long long mod) {
  long long tmp =
      (x * y - (long long)((long double)x / mod * y + 1.0e-8) * mod);
  return tmp < 0 ? tmp + mod : tmp;
}
struct np {
  int a, b;
  inline np() { a = b = 0; }
  inline np(int A, int B) {
    a = A;
    b = B;
  }
};
int n, m, i, j, s, o, k;
int fa[400005 << 1], sz1[400005 << 1], sz2[400005 << 1];
long long ans[400005];
map<int, map<int, int> > b;
inline int find(int x) {
  if (fa[x] == x) return x;
  return find(fa[x]);
}
vector<np> tre[400005 << 2];
stack<np> st[400005 * 3];
inline void addtree(int a, int l, int r, np y, int al, int ar) {
  if (al > r || ar < l) return;
  if (al >= l && ar <= r) {
    tre[a].push_back(y);
    return;
  }
  int mid = al + ar >> 1;
  addtree(a << 1, l, r, y, al, mid);
  addtree(a << 1 | 1, l, r, y, mid + 1, ar);
  return;
}
inline void pushdown(int a, int al, int ar, long long as) {
  for (int i = 0; i < tre[a].size(); i++) {
    s = tre[a][i].a;
    o = tre[a][i].b + 400005 - 5;
    int u = find(s), v = find(o);
    if (u != v) {
      if (sz1[u] + sz2[u] > sz1[v] + sz2[v]) swap(u, v), swap(s, o);
      fa[u] = v;
      as -= sz1[u] * 1ll * sz2[u] + sz1[v] * 1ll * sz2[v];
      sz1[v] += sz1[u];
      sz2[v] += sz2[u];
      as += sz1[v] * 1ll * sz2[v];
      st[a].push(np(u, v));
    }
  }
  if (al == ar) {
    ans[al] = as;
  } else {
    int mid = al + ar >> 1;
    pushdown(a << 1, al, mid, as);
    pushdown(a << 1 | 1, mid + 1, ar, as);
  }
  while (!st[a].empty()) {
    int u = st[a].top().a, v = st[a].top().b;
    st[a].pop();
    fa[u] = u;
    as -= sz1[v] * 1ll * sz2[v];
    sz1[v] -= sz1[u];
    sz2[v] -= sz2[u];
    as += sz1[u] * 1ll * sz2[u] + sz1[v] * 1ll * sz2[v];
  }
  return;
}
signed main() {
  m = read();
  stack<np> ss;
  for (int i = 1; i <= (400005 - 5 << 1); i++) {
    fa[i] = i;
    if (i <= 400005 - 5)
      sz1[i] = 1;
    else
      sz2[i] = 1;
  }
  for (int i = 1; i <= m; i++) {
    s = read();
    o = read();
    int ll;
    if (!(ll = b[s][o]))
      b[s][o] = i, ss.push(np(s, o));
    else
      addtree(1, ll, i - 1, np(s, o), 1, m), b[s][o] = 0;
  }
  while (!ss.empty()) {
    s = ss.top().a, o = ss.top().b;
    int ll;
    if (ll = b[s][o]) {
      addtree(1, ll, m, ss.top(), 1, m);
      b[s][o] = 0;
    }
    ss.pop();
  }
  pushdown(1, 1, m, 0ll);
  for (int i = 1; i <= m; i++) {
    printf("%lld ", ans[i]);
  }
  putchar('\n');
  return 0;
}