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 gi() {
  char cc = getchar();
  long long cn = 0, flus = 1;
  while (cc < '0' || cc > '9') {
    if (cc == '-') flus = -flus;
    cc = getchar();
  }
  while (cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar();
  return cn * flus;
}
const long long N = 6e5 + 5;
long long n, Ans, maxn, sz[N], cntx[N], cnty[N], fa[N], ans[N];
struct node {
  long long x, y;
};
struct Tr {
  vector<node> S;
} tr[N << 2];
map<pair<long long, long long>, long long> S;
void insert(long long x, long long l, long long r, long long ql, long long qr,
            node k) {
  if (ql <= l && r <= qr) return tr[x].S.push_back(k), void();
  if (qr < l || r < ql) return;
  long long mid = (l + r) >> 1;
  insert((x << 1), l, mid, ql, qr, k),
      insert((x << 1 | 1), mid + 1, r, ql, qr, k);
}
vector<node> q;
long long fd(long long x) { return (fa[x] == x) ? x : fd(fa[x]); }
void merge(long long x, long long y) {
  long long u = fd(x), v = fd(y);
  if (u == v) return;
  if (sz[u] > sz[v]) swap(u, v);
  Ans -= cntx[u] * cnty[u], Ans -= cntx[v] * cnty[v],
      fa[u] = v, cntx[v] += cntx[u], cnty[v] += cnty[u],
      Ans += cntx[v] * cnty[v], sz[v] += sz[u], q.push_back((node){u, v});
}
void solve(long long x, long long l, long long r) {
  if (l == r) {
    long long lsz = q.size();
    for (node v : tr[x].S) merge(v.x, v.y + maxn);
    ans[l] = Ans;
    long long siz = q.size();
    for (long long i = siz - 1; i >= lsz; --i) {
      long long u = q[i].x, v = q[i].y;
      Ans -= cntx[v] * cnty[v], fa[u] = u, cntx[v] -= cntx[u],
                                cnty[v] -= cnty[u], sz[v] -= sz[u];
      Ans += cntx[u] * cnty[u], Ans += cntx[v] * cnty[v];
    }
    while (q.size() > lsz) q.pop_back();
    return;
  }
  long long mid = (l + r) >> 1, lsz = q.size();
  for (node v : tr[x].S) merge(v.x, v.y + maxn);
  solve((x << 1), l, mid), solve((x << 1 | 1), mid + 1, r);
  long long siz = q.size();
  for (long long i = siz - 1; i >= lsz; --i) {
    long long u = q[i].x, v = q[i].y;
    Ans -= cntx[v] * cnty[v], fa[u] = u, cntx[v] -= cntx[u], cnty[v] -= cnty[u],
                              sz[v] -= sz[u];
    Ans += cntx[u] * cnty[u], Ans += cntx[v] * cnty[v];
  }
  while (q.size() > lsz) q.pop_back();
}
signed main() {
  n = gi();
  long long x, y;
  for (register long long i = (1); i <= (n); ++i) {
    x = gi(), y = gi(), maxn = max(max(x, y), maxn);
    if (S[make_pair(x, y)]) {
      node opt = (node){x, y};
      insert(1, 1, n, S[make_pair(x, y)], i - 1, opt), S[make_pair(x, y)] = 0;
    } else
      S[make_pair(x, y)] = i;
  }
  for (auto z : S)
    if (z.second)
      insert(1, 1, n, z.second, n, (node){z.first.first, z.first.second});
  for (register long long i = (1); i <= ((maxn * 2)); ++i) sz[i] = 1, fa[i] = i;
  for (register long long i = (1); i <= (maxn); ++i)
    cntx[i] = 1, cnty[i + maxn] = 1;
  solve(1, 1, n);
  for (register long long i = (1); i <= (n); ++i) printf("%lld ", ans[i]);
  return 0;
}