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>
const int N = 600010;
int n, from[N], to[N], st[N], ed[N], m, p[N], U[N], V[N], top;
int dep[N], fa[N], sz0[N], sz1[N];
long long res;
std::pair<int, int> stk[N];
std::vector<std::pair<int, int> > e[N << 2];
void modify(int rt, int L, int R, int l, int r, int u, int v) {
  if (l <= L && R <= r) {
    e[rt].push_back(std::make_pair(u, v));
    return;
  }
  int mid = (L + R) >> 1;
  if (l <= mid) modify(rt << 1, L, mid, l, r, u, v);
  if (r > mid) modify(rt << 1 | 1, mid + 1, R, l, r, u, v);
  return;
}
int Find(int x) {
  while (fa[x] != x) x = fa[x];
  return x;
}
void Merge(int u, int v) {
  if (dep[u] > dep[v]) std::swap(u, v);
  stk[++top].first = u;
  stk[top].second = (dep[u] == dep[v]);
  fa[u] = v;
  dep[v] += (dep[u] == dep[v]);
  res += 1LL * sz0[u] * sz1[v] + 1LL * sz1[u] * sz0[v];
  sz0[v] += sz0[u];
  sz1[v] += sz1[u];
}
void dfs(int rt, int l, int r) {
  int btop = top;
  for (int i = 0; i < e[rt].size(); i++) {
    int u = e[rt][i].first, v = e[rt][i].second;
    if (Find(u) != Find(v)) {
      Merge(Find(u), Find(v));
    }
  }
  if (l < r) {
    int mid = (l + r) >> 1;
    dfs(rt << 1, l, mid);
    dfs(rt << 1 | 1, mid + 1, r);
  } else
    printf("%lld ", res);
  while (top > btop) {
    int u = stk[top].first, f = fa[u];
    fa[u] = u;
    dep[f] -= stk[top].second;
    sz0[f] -= sz0[u];
    sz1[f] -= sz1[u];
    res -= (1LL * sz0[u] * sz1[f] + 1LL * sz0[f] * sz1[u]);
    top--;
  }
}
std::map<std::pair<int, int>, int> mp;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &from[i], &to[i]);
    to[i] += 300000;
    if (mp[std::make_pair(from[i], to[i])]) {
      st[++m] = mp[std::make_pair(from[i], to[i])];
      ed[m] = i;
      mp[std::make_pair(from[i], to[i])] = 0;
      p[st[m]] = p[ed[m]] = 1;
      U[m] = from[i];
      V[m] = to[i];
    } else
      mp[std::make_pair(from[i], to[i])] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (!p[i]) {
      st[++m] = i;
      ed[m] = n + 1;
      U[m] = from[i];
      V[m] = to[i];
    }
  }
  for (int i = 1; i <= m; i++) {
    modify(1, 1, n, st[i], ed[i] - 1, U[i], V[i]);
  }
  for (int i = 1; i <= N - 10; i++) {
    fa[i] = i, dep[i] = 1;
    sz0[i] = (i <= 300000);
    sz1[i] = (i > 300000);
  }
  dfs(1, 1, n);
  return 0;
}