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 
#include <bits/stdc++.h>
using namespace std;
long long inline read() {
  long long num = 0, neg = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num * neg;
}
const long long maxn = 300010;
long long n, u[maxn], v[maxn], vis[maxn], is[maxn];
map<long long, map<long long, long long> > m;
vector<long long> M[maxn << 2];
void update(long long x, long long l, long long r, long long L, long long R,
            long long id) {
  if (l >= L && r <= R) {
    M[x].push_back(id);
    return;
  }
  long long mid = l + r >> 1;
  if (mid >= L) update(x << 1, l, mid, L, R, id);
  if (mid < R) update(x << 1 | 1, mid + 1, r, L, R, id);
}
long long N = 300000, fa[maxn << 1], d[maxn << 1], szx[maxn << 1],
          szy[maxn << 1], ans, tp;
struct Node {
  long long d, x, delta, szx, szy;
} stk[maxn];
long long Find(long long x) { return x == fa[x] ? x : Find(fa[x]); }
void Merge(long long x, long long y) {
  x = Find(x);
  y = Find(y);
  if (x == y) return;
  long long sum = 0;
  if (d[x] > d[y]) swap(x, y);
  fa[x] = y;
  sum -= szx[x] * szy[x] + szx[y] * szy[y];
  szx[y] += szx[x];
  szy[y] += szy[x];
  sum += szx[y] * szy[y];
  ans += sum;
  if (d[x] + 1 > d[y]) d[y] = d[x] + 1;
  stk[++tp] = (Node){d[x] + 1 > d[y], x, sum, szx[x], szy[x]};
}
void dfs(long long x, long long l, long long r) {
  long long len = tp, mid = l + r >> 1;
  for (long long i = 0; i < M[x].size(); i++) {
    long long id = M[x][i];
    Merge(u[id], v[id]);
  }
  if (l == r)
    printf("%lld ", ans);
  else
    dfs(x << 1, l, mid), dfs(x << 1 | 1, mid + 1, r);
  while (tp > len) {
    d[fa[stk[tp].x]] -= stk[tp].d;
    szx[fa[stk[tp].x]] -= stk[tp].szx;
    szy[fa[stk[tp].x]] -= stk[tp].szy;
    fa[stk[tp].x] = stk[tp].x;
    ans -= stk[tp].delta;
    tp--;
  }
}
signed main() {
  n = read();
  long long cnt = 0;
  for (long long i = 1; i <= n; i++) {
    u[i] = read();
    v[i] = read() + N;
    is[i] = 1;
    if (m[u[i]][v[i]])
      is[m[u[i]][v[i]]] = 0, is[i] = 0, vis[i] = m[u[i]][v[i]],
      m[u[i]][v[i]] = 0;
    else
      m[u[i]][v[i]] = i;
  }
  for (long long i = 1; i <= n; i++)
    if (is[i]) update(1, 1, n, i, n, i);
  for (long long i = 1; i <= n; i++)
    if (vis[i]) update(1, 1, n, vis[i], i - 1, vis[i]);
  for (long long i = 1; i <= 2 * N; i++) {
    fa[i] = i;
    if (i <= N)
      szx[i] = 1;
    else
      szy[i] = 1;
  }
  dfs(1, 1, n);
  return 0;
}
