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;
long long read() {
  long long x = 0, F = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') F = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  return x * F;
}
int add(int a, int b) {
  return (a + b >= 1000000007) ? a + b - 1000000007 : a + b;
}
int dec(int a, int b) { return (a - b < 0) ? a - b + 1000000007 : a - b; }
int mul(int a, int b) { return 1LL * a * b % 1000000007; }
int fst_pow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
int inv(int a) { return fst_pow(a, 1000000007 - 2); }
int n, m, cnt;
struct query {
  int l, r;
  pair<int, int> a;
} q[(300000 << 1) + 5];
struct rec {
  int a, b;
} stk[(300000 << 1) + 5];
int fa[(300000 << 1) + 5], cx[(300000 << 1) + 5], cy[(300000 << 1) + 5], tp;
map<pair<int, int>, int> D;
long long ans;
int xfind(int x) { return (fa[x] == x) ? x : xfind(fa[x]); }
struct Seg_tree {
  vector<pair<int, int> > p[(300000 << 2) + 5];
  void merge(int u, int v) {
    u = xfind(u), v = xfind(v);
    if (u == v) return;
    ans -= 1LL * cx[u] * cy[u] + 1LL * cx[v] * cy[v];
    if (cx[u] + cy[u] < cx[v] + cy[v]) swap(u, v);
    cx[u] += cx[v], cy[u] += cy[v];
    fa[v] = u;
    stk[++tp] = (rec){u, v};
    ans += 1LL * cx[u] * cy[u];
  }
  void recycle(int u, int v) {
    ans -= 1LL * cx[u] * cy[u];
    fa[v] = v, cx[u] -= cx[v], cy[u] -= cy[v];
    ans += 1LL * cx[u] * cy[u] + 1LL * cx[v] * cy[v];
  }
  void Insert(int x, int l, int r, int L, int R, pair<int, int> e) {
    if (L > r || R < l) return;
    if (L <= l && r <= R) {
      p[x].push_back(e);
      return;
    }
    int mid = (l + r) >> 1;
    Insert((x << 1), l, mid, L, R, e);
    Insert((x << 1 | 1), mid + 1, r, L, R, e);
  }
  void solve(int x, int l, int r) {
    int pt = tp;
    for (int i = 0; i < p[x].size(); i++) merge(p[x][i].first, p[x][i].second);
    int mid = (l + r) >> 1;
    if (l == r)
      printf("%lld ", ans);
    else
      solve((x << 1), l, mid), solve((x << 1 | 1), mid + 1, r);
    while (tp > pt) recycle(stk[tp].a, stk[tp].b), tp--;
  }
} T;
int main() {
  n = 300000, m = read();
  for (int i = 1; i <= m; i++) {
    int u = read(), v = read() + n;
    pair<int, int> tmp = pair<int, int>(u, v);
    if (D.count(tmp)) {
      q[D[tmp]].r = i - 1;
      D.erase(tmp);
    } else {
      D[tmp] = ++cnt;
      q[cnt] = (query){i, m, tmp};
    }
  }
  for (int i = 1; i <= cnt; i++) T.Insert(1, 1, m, q[i].l, q[i].r, q[i].a);
  for (int i = 1; i <= 2 * n; i++) cx[i] = (i <= n), cy[i] = (i > n), fa[i] = i;
  T.solve(1, 1, m);
}