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>
#pragma GCC optimize(3)
using namespace std;
const long long inff = 0x3f3f3f3f3f3f3f3f;
int fa[600008], sx[600008], sy[600008], n;
long long ans = 0;
int fid(int x) { return (fa[x] ^ x) ? fid(fa[x]) : x; }
unordered_map<int, int> mp[300008];
struct ass {
  int x, y;
} a[300008];
struct as {
  int l, r;
  vector<pair<int, int> > g;
} tr[300008 << 2];
void build(int d, int l, int r) {
  tr[d].l = l, tr[d].r = r;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(d << 1, l, mid);
  build(d << 1 | 1, mid + 1, r);
}
void add(int d, int l, int r, pair<int, int> pos) {
  if (tr[d].l == l && tr[d].r == r) {
    tr[d].g.push_back(pos);
    return;
  }
  int mid = (tr[d].l + tr[d].r) >> 1;
  if (mid >= r)
    add(d << 1, l, r, pos);
  else if (l > mid)
    add(d << 1 | 1, l, r, pos);
  else
    add(d << 1, l, mid, pos), add(d << 1 | 1, mid + 1, r, pos);
}
void query(int d) {
  vector<int> st;
  for (auto it : tr[d].g) {
    int fx = fid(it.first), fy = fid(it.second);
    if (fx == fy) continue;
    if (sx[fx] + sy[fx] < sx[fy] + sy[fy]) swap(fx, fy);
    ans -= (1ll * sx[fx] * sy[fx] + 1ll * sy[fy] * sx[fy]);
    fa[fy] = fx, sx[fx] += sx[fy];
    sy[fx] += sy[fy];
    ans += 1ll * sx[fx] * sy[fx];
    st.push_back(fy);
  }
  if (tr[d].l == tr[d].r)
    printf("%lld ", ans);
  else
    query(d << 1), query(d << 1 | 1);
  for (int i = st.size() - 1; i >= 0; i--) {
    ans -= 1ll * sx[fa[st[i]]] * sy[fa[st[i]]];
    sx[fa[st[i]]] -= sx[st[i]], sy[fa[st[i]]] -= sy[st[i]];
    ans += (1ll * sx[fa[st[i]]] * sy[fa[st[i]]] + 1ll * sx[st[i]] * sy[st[i]]);
    fa[st[i]] = st[i];
  }
  st.clear();
}
int main() {
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  build(1, 1, n);
  for (int i(1); i <= (300000); ++i) fa[i] = i, sx[i] = 1;
  for (int i(300001); i <= (600000); ++i) fa[i] = i, sy[i] = 1;
  for (int i(1); i <= (n); ++i) {
    scanf("%d", &a[i].x), scanf("%d", &a[i].y);
    if (mp[a[i].x][a[i].y]) {
      add(1, mp[a[i].x][a[i].y], i - 1,
          pair<int, int>(a[i].x, a[i].y + 300000));
      mp[a[i].x][a[i].y] = 0;
      continue;
    }
    mp[a[i].x][a[i].y] = i;
  }
  for (int i(1); i <= (n); ++i)
    if (mp[a[i].x][a[i].y])
      add(1, mp[a[i].x][a[i].y], n, pair<int, int>(a[i].x, a[i].y + 300000));
  query(1);
  puts("");
  return 0;
}