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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXQ = 300000;
const int MAXN = 2 * MAXQ;
int nq;
int qx[MAXQ], qy[MAXQ];
long long qans[MAXQ];
int allx[MAXQ], nallx;
int ally[MAXQ], nally;
int qmatch[MAXQ];
vector<int> changes;
int par[MAXN], lsz[MAXN], rsz[MAXN];
long long sum;
int uffind(int x) {
  while (x != par[x]) x = par[x];
  return x;
}
void addedge(int idx) {
  int a = qx[idx], b = nallx + qy[idx];
  a = uffind(a), b = uffind(b);
  if (a == b) return;
  if (lsz[a] + rsz[a] < lsz[b] + rsz[b]) swap(a, b);
  changes.push_back(b);
  sum -= (long long)lsz[a] * rsz[a] + (long long)lsz[b] * rsz[b];
  lsz[a] += lsz[b], rsz[a] += rsz[b], par[b] = a;
  sum += (long long)lsz[a] * rsz[a];
}
void rollback(int upto) {
  while (((int)(changes).size()) > upto) {
    int b = changes.back(), a = par[b];
    changes.pop_back();
    sum -= (long long)lsz[a] * rsz[a];
    lsz[a] -= lsz[b], rsz[a] -= rsz[b], par[b] = b;
    sum += (long long)lsz[a] * rsz[a] + (long long)lsz[b] * rsz[b];
  }
}
void rec(int ql, int qr) {
  if (ql == qr) {
    qans[ql] = sum;
  } else {
    int qm = ql + (qr - ql) / 2;
    int loldchanges = ((int)(changes).size());
    for (int i = (qm + 1); i <= (qr); ++i)
      if (qmatch[i] != -1 && qmatch[i] <= ql) addedge(i);
    rec(ql, qm);
    rollback(loldchanges);
    int roldchanges = ((int)(changes).size());
    for (int i = (ql + 1); i <= (qm + 1); ++i)
      if (qmatch[i] == -1 || qmatch[i] > qr) addedge(i);
    rec(qm + 1, qr);
    rollback(roldchanges);
  }
}
void solve() {
  nallx = 0;
  for (int i = (0); i < (nq); ++i) allx[nallx++] = qx[i];
  sort(allx, allx + nallx);
  nallx = unique(allx, allx + nallx) - allx;
  for (int i = (0); i < (nq); ++i)
    qx[i] = lower_bound(allx, allx + nallx, qx[i]) - allx;
  nally = 0;
  for (int i = (0); i < (nq); ++i) ally[nally++] = qy[i];
  sort(ally, ally + nally);
  nally = unique(ally, ally + nally) - ally;
  for (int i = (0); i < (nq); ++i)
    qy[i] = lower_bound(ally, ally + nally, qy[i]) - ally;
  map<pair<int, int>, int> mp;
  for (int i = (0); i < (nq); ++i) {
    pair<int, int> key = make_pair(qx[i], qy[i]);
    if (!mp.count(key)) {
      qmatch[i] = -1;
      mp[key] = i;
    } else {
      qmatch[i] = mp[key];
      mp.erase(key);
      qmatch[qmatch[i]] = i;
    }
  }
  sum = 0;
  for (int i = (0); i < (nallx + nally); ++i)
    par[i] = i, lsz[i] = i < nallx ? 1 : 0, rsz[i] = i < nallx ? 0 : 1;
  if (qmatch[0] == -1) addedge(0);
  rec(0, nq - 1);
}
void run() {
  scanf("%d", &nq);
  for (int i = (0); i < (nq); ++i) scanf("%d%d", &qx[i], &qy[i]);
  solve();
  for (int i = (0); i < (nq); ++i) {
    if (i != 0) printf(" ");
    printf("%lld", qans[i]);
  }
  puts("");
}
int main() {
  run();
  return 0;
}