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 = 300010, N = 300000;
const int inf = 2147483647;
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x * f;
}
int n, fa[Maxn << 1], sx[Maxn << 1], sy[Maxn << 1];
int findfa(int x) { return ((fa[x] == x) ? x : findfa(fa[x])); }
struct Edge {
  int x, y, l, r;
} e[Maxn];
int le;
struct Seg {
  int l, r, lc, rc;
} tr[Maxn << 1];
vector<int> h[Maxn << 1];
int tot = 0;
void build(int l, int r) {
  int x = ++tot;
  tr[x].l = l;
  tr[x].r = r;
  if (l == r) return;
  int mid = l + r >> 1;
  tr[x].lc = tot + 1, build(l, mid);
  tr[x].rc = tot + 1, build(mid + 1, r);
}
void ins(int x, int l, int r, int id) {
  if (tr[x].l == l && tr[x].r == r) {
    h[x].push_back(id);
    return;
  }
  int lc = tr[x].lc, rc = tr[x].rc, mid = tr[x].l + tr[x].r >> 1;
  if (r <= mid)
    ins(lc, l, r, id);
  else if (l > mid)
    ins(rc, l, r, id);
  else
    ins(lc, l, mid, id), ins(rc, mid + 1, r, id);
}
unordered_map<int, int> mp[Maxn];
long long ans[Maxn];
pair<int, int> sta[Maxn];
int top = 0;
long long cur = 0;
void dfs(int x) {
  int t = top;
  long long cc = cur;
  for (int i = 0; i < h[x].size(); i++) {
    int fx = findfa(e[h[x][i]].x), fy = findfa(e[h[x][i]].y);
    if (fx == fy) continue;
    if (sx[fx] + sy[fx] > sx[fy] + sy[fy]) swap(fx, fy);
    cur -= (long long)sx[fx] * sy[fx], cur -= (long long)sx[fy] * sy[fy];
    sx[fy] += sx[fx], sy[fy] += sy[fx];
    cur += (long long)sx[fy] * sy[fy];
    fa[fx] = fy;
    sta[++top] = make_pair(fx, fy);
  }
  if (tr[x].l == tr[x].r)
    ans[tr[x].l] = cur;
  else
    dfs(tr[x].lc), dfs(tr[x].rc);
  while (top > t) {
    int fx = sta[top].first, fy = sta[top].second;
    top--;
    cur -= (long long)sx[fy] * sy[fy];
    sx[fy] -= sx[fx], sy[fy] -= sy[fx];
    cur += (long long)sx[fx] * sy[fx], cur += (long long)sx[fy] * sy[fy];
    fa[fx] = fx;
  }
}
int main() {
  n = read();
  for (int i = 1; i <= N; i++) fa[i] = i, sx[i] = 1, sy[i] = 0;
  for (int i = N + 1; i <= (N << 1); i++) fa[i] = i, sx[i] = 0, sy[i] = 1;
  for (int i = 1; i <= n; i++) {
    int x = read(), y = read();
    if (!mp[x][y]) {
      ++le;
      e[le].x = x;
      e[le].y = y + N;
      e[le].l = i;
      e[le].r = n;
      mp[x][y] = le;
    } else
      e[mp[x][y]].r = i - 1, mp[x][y] = 0;
  }
  build(1, n);
  for (int i = 1; i <= le; i++) ins(1, e[i].l, e[i].r, i);
  dfs(1);
  for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}