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 = 3e5 + 50;
vector<pair<int, int> > rt[maxn << 2];
void update(int o, int l, int r, int ql, int qr, pair<int, int> pi) {
  if (ql <= l && qr >= r) {
    rt[o].push_back(pi);
    return;
  }
  int mid = (l + r) / 2;
  if (ql <= mid) update(o << 1, l, mid, ql, qr, pi);
  if (qr > mid) update(o << 1 | 1, mid + 1, r, ql, qr, pi);
}
int fa[maxn << 1];
long long sz[maxn << 1], szx[maxn << 1], szy[maxn << 1];
int find(int x) {
  if (fa[x] == x) return x;
  return find(fa[x]);
}
long long value;
long long ans[maxn];
void ins(int x, int y, stack<pair<int, int> > &st) {
  int xx = find(x);
  int yy = find(y);
  if (xx == yy) return;
  if (sz[xx] < sz[yy]) swap(xx, yy);
  st.push({xx, yy});
  value -= 1LL * szx[yy] * szy[yy];
  value -= 1LL * szx[xx] * szy[xx];
  sz[xx] += 1LL * sz[yy];
  szx[xx] += 1LL * szx[yy];
  szy[xx] += 1LL * szy[yy];
  value += 1LL * szx[xx] * szy[xx];
  fa[yy] = fa[xx];
}
void del(stack<pair<int, int> > &st) {
  while (!st.empty()) {
    int x = st.top().first;
    int y = st.top().second;
    st.pop();
    value -= 1LL * szx[x] * szy[x];
    sz[x] -= 1LL * sz[y];
    szx[x] -= 1LL * szx[y];
    szy[x] -= 1LL * szy[y];
    fa[y] = y;
    value += 1LL * szx[x] * szy[x];
    value += 1LL * szx[y] * szy[y];
  }
}
void dfs(int o, int l, int r) {
  stack<pair<int, int> > st;
  for (auto i : rt[o]) {
    int x = i.first;
    int y = i.second;
    ins(x, y, st);
  }
  if (l == r)
    ans[l] = value;
  else {
    int mid = (l + r) / 2;
    dfs(o << 1, l, mid);
    dfs(o << 1 | 1, mid + 1, r);
  }
  del(st);
}
map<pair<int, int>, int> mp;
int main() {
  int q;
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int x, y;
    cin >> x >> y;
    y += 3e5;
    pair<int, int> pi = make_pair(x, y);
    if (mp.find(pi) == mp.end()) {
      mp[pi] = i;
    } else {
      update(1, 1, q, mp[pi], i - 1, pi);
      mp.erase(pi);
    }
  }
  for (auto i : mp) {
    update(1, 1, q, i.second, q, i.first);
  }
  for (int i = 1; i <= 3e5; i++) {
    fa[i] = i;
    sz[i] = 1;
    szx[i] = 1;
  }
  for (int i = 3e5 + 1; i <= 6e5; i++) {
    fa[i] = i;
    szy[i] = 1;
    sz[i] = 1;
  }
  dfs(1, 1, q);
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << " ";
  }
  return 0;
}