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 void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while ((c = getchar()) == ' ')
    ;
  x = c;
}
inline void writes(string s) { puts(s.c_str()); }
inline void writeln() { writes(""); }
inline void writei(int x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
inline void writell(long long x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
long long n, m, i, j, fa[600005], sz1[600005], sz2[600005], x, y, ans;
stack<long long> stk1, stk2;
map<pair<long long, long long>, long long> lst;
vector<pair<long long, long long> > lys[2400005];
int fnd(int x) {
  if (fa[x] == x) {
    return x;
  }
  return fnd(fa[fa[fa[fa[x]]]]);
}
int merge(int x, int y) {
  x = fnd(x);
  y = fnd(y);
  if (x == y) return 0;
  if (sz1[x] + sz2[x] > sz1[y] + sz2[y]) swap(x, y);
  ans -= sz1[x] * sz2[x];
  ans -= sz1[y] * sz2[y];
  sz1[y] += sz1[x];
  sz2[y] += sz2[x];
  fa[x] = y;
  ans += sz1[y] * sz2[y];
  stk1.push(x);
  stk2.push(y);
  return 1;
}
void undo() {
  int x = stk1.top(), y = stk2.top();
  stk1.pop();
  stk2.pop();
  ans -= sz1[y] * sz2[y];
  fa[x] = x;
  sz1[y] -= sz1[x];
  sz2[y] -= sz2[x];
  ans += sz1[x] * sz2[x];
  ans += sz1[y] * sz2[y];
}
void update(int x, int tl, int tr, int l, int r, pair<int, int> f) {
  if (tl > r || tr < l) {
    return;
  }
  if (tl >= l && tr <= r) {
    lys[x].push_back(f);
    return;
  }
  update(x * 2, tl, (tl + tr) / 2, l, r, f);
  update(x * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, f);
}
void solve(int x, int l, int r) {
  int cnt = 0;
  for (__typeof((lys[x]).begin()) it = (lys[x]).begin(); it != (lys[x]).end();
       it++) {
    cnt += merge(it->first, it->second);
  }
  if (l == r) {
    printf("%I64d ", ans);
    while (cnt--) {
      undo();
    }
    return;
  }
  solve(x * 2, l, (l + r) / 2);
  solve(x * 2 + 1, (l + r) / 2 + 1, r);
  while (cnt--) {
    undo();
  }
}
int main() {
  read(n);
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    read(x);
    read(y);
    if (!lst.count(make_pair(x, y))) {
      lst[make_pair(x, y)] = i;
    } else {
      update(1, 1, n, lst[make_pair(x, y)], i - 1, make_pair(x, y + 300000));
      lst.erase(make_pair(x, y));
    }
  }
  for (__typeof((lst).begin()) it = (lst).begin(); it != (lst).end(); it++) {
    update(1, 1, n, it->second, n,
           make_pair(it->first.first, it->first.second + 300000));
  }
  for (((i)) = (1); ((i)) <= ((600000)); ((i))++) {
    fa[i] = i;
    if (i <= 300000)
      sz1[i] = 1;
    else
      sz2[i] = 1;
  }
  solve(1, 1, n);
  return 0;
}