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 MAXN = 600015;
const int MAXC = 300003;
const long long MOD = 1000000007;
struct Log {
  int u, v;
  long long szux, szuy, szvx, szvy, ans;
};
vector<Log> logs;
int djs[MAXN], q;
long long ans, res[MAXN], szx[MAXN], szy[MAXN];
map<pair<int, int>, int> lst;
int fnd(int x) { return x == djs[x] ? x : fnd(djs[x]); }
void uni(int x, int y) {
  x = fnd(x);
  y = fnd(y);
  logs.push_back({x, y, szx[x], szy[x], szx[y], szy[y], ans});
  if (x != y) {
    if (szx[x] + szy[x] > szx[y] + szy[y]) {
      swap(x, y);
    }
    djs[x] = y;
    ans -= szx[x] * szy[x] + szx[y] * szy[y];
    szx[y] += szx[x];
    szy[y] += szy[x];
    ans += szx[y] * szy[y];
  }
}
void undo() {
  assert(!logs.empty());
  Log cur = logs.back();
  logs.pop_back();
  ans = cur.ans;
  djs[cur.u] = cur.u;
  djs[cur.v] = cur.v;
  szx[cur.u] = cur.szux;
  szy[cur.u] = cur.szuy;
  szx[cur.v] = cur.szvx;
  szy[cur.v] = cur.szvy;
}
vector<pair<int, int> > seg[MAXN * 4];
void add_query(pair<int, int> cur, int qL, int qR, int v = 1, int nL = 0,
               int nR = q) {
  if (qL >= nR || qR <= nL || qL >= qR) {
    return;
  } else if (qL <= nL && nR <= qR) {
    seg[v].emplace_back(cur);
    ;
  } else {
    int nM = (nL + nR) >> 1;
    add_query(cur, qL, qR, v << 1, nL, nM);
    add_query(cur, qL, qR, v << 1 | 1, nM, nR);
  }
}
void time_dfs(int v = 1, int l = 0, int r = q) {
  for (auto p : seg[v]) {
    uni(p.first, p.second);
  }
  if (l == r - 1) {
    res[l] = ans;
  } else {
    int m = (l + r) >> 1;
    time_dfs(v << 1, l, m);
    time_dfs(v << 1 | 1, m, r);
  }
  for (int i = 0; i < int(seg[v].size()); i++) {
    undo();
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  for (int i = 1; i <= MAXC; i++) {
    djs[i] = i;
    djs[i + MAXC] = i + MAXC;
    szx[i] = 1;
    szy[i + MAXC] = 1;
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    y += MAXC;
    if (lst.count({x, y})) {
      add_query({x, y}, lst[{x, y}], i);
      lst.erase({x, y});
    } else {
      lst[{x, y}] = i;
    }
  }
  for (auto p : lst) {
    add_query(p.first, p.second, q);
  }
  time_dfs();
  for (int i = 0; i < q; i++) {
    cout << res[i] << " \n"[i == q - 1];
  }
  return 0;
}