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;
const int MAX = 6e5 + 5;
int br[MAX];
int* fa = (br + MAX / 2);
long long cr[MAX];
long long* xd = (cr + MAX / 2);
long long dr[MAX];
long long* yd = (dr + MAX / 2);
long long ans[MAX];
long long A;
inline long long qs(int a) { return xd[a] + yd[a]; }
int que(int x) { return x == fa[x] ? x : que(fa[x]); }
pair<int, int> uni(int a, int b) {
  a = que(a);
  b = que(b);
  if (a == b) return pair<int, int>(0, 0);
  if (qs(a) > qs(b)) swap(a, b);
  fa[a] = b;
  A -= xd[b] * yd[b] + xd[a] * yd[a];
  xd[b] += xd[a];
  yd[b] += yd[a];
  A += xd[b] * yd[b];
  return pair<int, int>(a, b);
}
void bk(int a, int b) {
  if (fa[b] == a) swap(a, b);
  A -= xd[b] * yd[b];
  xd[b] -= xd[a];
  yd[b] -= yd[a];
  A += xd[b] * yd[b] + xd[a] * yd[a];
  fa[a] = a;
  return;
}
struct B {
  int l, r, x, y;
  B(int a, int b, int c, int d) {
    l = a;
    r = b;
    x = c;
    y = d;
  }
};
void dfs(int l, int r, vector<B>& vec) {
  vector<B> L, R;
  vector<pair<int, int> > v;
  int md = l + r >> 1;
  for (auto b : vec) {
    if (b.l <= l && r <= b.r)
      v.emplace_back(uni(b.x, b.y));
    else {
      if (b.l < md) L.emplace_back(b);
      if (md < b.r) R.emplace_back(b);
    }
  }
  if (L.size() + R.size() == 0)
    for (int i = l; i < r; i++) ans[i] = A;
  else {
    dfs(l, md, L);
    dfs(md, r, R);
  }
  reverse(v.begin(), v.end());
  for (pair<int, int> ii : v) bk(ii.first, ii.second);
  return;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> q;
  for (int i = 1; i <= 300000; i++) {
    fa[i] = i;
    xd[i] = 1;
    fa[-i] = -i;
    yd[-i] = 1;
  }
  map<pair<int, int>, int> mpp;
  vector<B> vec;
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    y = -y;
    if (mpp.find(pair<int, int>(x, y)) == mpp.end())
      mpp[pair<int, int>(x, y)] = i;
    else {
      vec.emplace_back(mpp[pair<int, int>(x, y)], i, x, y);
      mpp.erase(pair<int, int>(x, y));
    }
  }
  for (auto ii : mpp)
    vec.emplace_back(ii.second, q, ii.first.first, ii.first.second);
  mpp.clear();
  dfs(0, q, vec);
  for (int i = 0; i < q; i++) {
    cout << ans[i] << ' ';
  }
  return 0;
}