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 n, m, a1, a2, ans, num, top, fa[600005], sx[600005], sy[600005],
    stl[600005], stt[600005][3];
pair<long long, long long> pa;
map<pair<long long, long long>, long long> mp;
vector<pair<long long, long long>> vec[600005 * 2];
vector<long long> q[600005];
struct node {
  long long l, r, id;
  node *ch[2];
} * nil, *root;
long long gets() {
  long long v = 0;
  char ch;
  bool f = 0;
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = 1;
  v = ch - 48;
  while (isdigit(ch = getchar())) v = (v << 1) + (v << 3) + ch - 48;
  return f ? -v : v;
}
long long getfa(long long x) { return fa[x] == x ? x : getfa(fa[x]); }
void init() {
  nil = new node();
  nil->ch[0] = nil->ch[1] = nil;
  nil->l = nil->r = nil->id = 0;
}
void build(node *&x, long long l, long long r) {
  x = new node();
  x->l = l, x->r = r;
  x->id = ++num;
  if (l == r) return;
  long long mid = l + r >> 1;
  build(x->ch[0], l, mid);
  build(x->ch[1], mid + 1, r);
}
void change(node *x, long long l, long long r, pair<long long, long long> val) {
  if (l == x->l && r == x->r) {
    vec[x->id].push_back(val);
    return;
  }
  long long mid = x->l + x->r >> 1;
  if (l > mid)
    change(x->ch[1], l, r, val);
  else if (r <= mid)
    change(x->ch[0], l, r, val);
  else
    change(x->ch[0], l, mid, val), change(x->ch[1], mid + 1, r, val);
}
void dfs(node *x) {
  pair<long long, long long> tmp;
  long long t1, t2, fa1, fa2;
  if (vec[x->id].size())
    for (int i = 0; i <= vec[x->id].size() - 1; i++) {
      tmp = vec[x->id][i];
      t1 = tmp.first, t2 = tmp.second;
      fa1 = getfa(t1), fa2 = getfa(t2);
      if (fa1 == fa2) {
        q[x->id].push_back(-1);
        continue;
      }
      if (sx[fa1] + sy[fa1] < sx[fa2] + sy[fa2]) {
        q[x->id].push_back(fa1);
        ans -= sx[fa2] * sy[fa2];
        ans -= sx[fa1] * sy[fa1];
        sx[fa2] += sx[fa1];
        sy[fa2] += sy[fa1];
        ans += sx[fa2] * sy[fa2];
        fa[fa1] = fa2;
      } else {
        q[x->id].push_back(fa2);
        ans -= sx[fa1] * sy[fa1];
        ans -= sx[fa2] * sy[fa2];
        sx[fa1] += sx[fa2];
        sy[fa1] += sy[fa2];
        ans += sx[fa1] * sy[fa1];
        fa[fa2] = fa1;
      }
    }
  if (x->l == x->r) {
    if (x->l == n)
      printf("%I64d\n", ans);
    else
      printf("%I64d ", ans);
  } else
    dfs(x->ch[0]), dfs(x->ch[1]);
  if (vec[x->id].size())
    for (long long i = q[x->id].size() - 1; i >= 0; i--) {
      fa1 = q[x->id][i];
      if (fa1 == -1) continue;
      fa2 = getfa(fa1);
      ans -= sx[fa2] * sy[fa2];
      sx[fa2] -= sx[fa1], sy[fa2] -= sy[fa1];
      ans += sx[fa2] * sy[fa2];
      ans += sx[fa1] * sy[fa1];
      fa[fa1] = fa1;
    }
}
int main() {
  n = gets();
  m = 300000;
  init();
  build(root, 1, n);
  for (int i = 1; i <= n; i++) {
    a1 = gets(), a2 = gets() + m;
    pa = pair<long long, long long>(a1, a2);
    if (mp[pa]) {
      change(root, mp[pa], i - 1, pa);
      stl[mp[pa]] = 0;
      mp.erase(mp.find(pa));
    } else
      mp[pa] = i, stl[i] = 1, stt[i][1] = a1, stt[i][2] = a2;
  }
  for (int i = 1; i <= n; i++)
    if (stl[i]) {
      pa = pair<long long, long long>(stt[i][1], stt[i][2]);
      change(root, i, n, pa);
    }
  for (int i = 1; i <= m; i++) fa[i] = i, sx[i] = 1, sy[i] = 0;
  for (int i = 1; i <= m; i++) fa[i + m] = i + m, sx[i + m] = 0, sy[i + m] = 1;
  dfs(root);
  return 0;
}