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 = 300005;
inline int readint() {
  int res = 0, f = 1;
  char c = 0;
  while (!isdigit(c)) {
    c = getchar();
    if (c == '-') f = -1;
  }
  while (isdigit(c)) res = res * 10 + c - '0', c = getchar();
  return res * f;
}
int n, fa[MAXN * 2], size[MAXN * 2][2];
long long nowans;
struct Info {
  int type, idx, fa, size0, size1;
  Info(int t = 0, int a = 0, int b = 0, int c = 0, int d = 0) {
    type = t, idx = a, fa = b, size0 = c, size1 = d;
  }
};
inline int getFather(int v) { return fa[v] == v ? v : getFather(fa[v]); }
inline void merge(int x, int y, vector<Info> &s) {
  int fx = getFather(x), fy = getFather(y);
  if (fx == fy) return;
  nowans += 1ll * size[fx][0] * size[fy][1] + 1ll * size[fx][1] * size[fy][0];
  if (size[fx][0] + size[fx][1] < size[fy][0] + size[fy][1]) {
    s.push_back(Info(0, fx, fa[fx], 0, 0));
    s.push_back(Info(1, fy, 0, size[fy][0], size[fy][1]));
    fa[fx] = fy, size[fy][0] += size[fx][0], size[fy][1] += size[fx][1];
  } else {
    s.push_back(Info(0, fy, fa[fy], 0, 0));
    s.push_back(Info(1, fx, 0, size[fx][0], size[fx][1]));
    fa[fy] = fx, size[fx][0] += size[fy][0], size[fx][1] += size[fy][1];
  }
}
inline void undo(vector<Info> &s) {
  while (!s.empty()) {
    Info now = s[s.size() - 1];
    if (now.type == 0)
      fa[now.idx] = now.fa;
    else {
      int s0 = now.size0, s1 = now.size1;
      nowans -= 1ll * size[now.idx][0] * size[now.idx][1];
      nowans += 1ll * s0 * s1 +
                1ll * (size[now.idx][0] - s0) * (size[now.idx][1] - s1);
      size[now.idx][0] = s0, size[now.idx][1] = s1;
    }
    s.pop_back();
  }
}
struct Node {
  vector<pair<int, int> > op;
  vector<Info> s;
  Node() { op.clear(), s.clear(); }
} t[MAXN << 2];
long long ans[MAXN];
inline void modify(int id, int ql, int qr, int l, int r, pair<int, int> d) {
  if (ql == l && qr == r) {
    t[id].op.push_back(d);
    return;
  }
  int mid = (ql + qr) >> 1;
  if (r <= mid)
    modify(id << 1, ql, mid, l, r, d);
  else if (l > mid)
    modify(id << 1 | 1, mid + 1, qr, l, r, d);
  else
    modify(id << 1, ql, mid, l, mid, d),
        modify(id << 1 | 1, mid + 1, qr, mid + 1, r, d);
}
inline void dfs(int id, int ql, int qr) {
  for (int i = 0; i < t[id].op.size(); i++) {
    merge(t[id].op[i].first, t[id].op[i].second + 300000, t[id].s);
  }
  if (ql != qr) {
    int mid = (ql + qr) >> 1;
    dfs(id << 1, ql, mid), dfs(id << 1 | 1, mid + 1, qr);
  } else
    ans[ql] = nowans;
  undo(t[id].s);
}
map<pair<int, int>, int> tim;
map<pair<int, int>, int>::iterator it;
int main() {
  n = readint();
  for (int i = 1; i <= 300000; i++) fa[i] = i, size[i][0] = 1, size[i][1] = 0;
  for (int i = 300001; i <= 600000; i++)
    fa[i] = i, size[i][0] = 0, size[i][1] = 1;
  for (int i = 1; i <= n; i++) {
    int x = readint(), y = readint();
    pair<int, int> now = make_pair(x, y);
    if (tim.find(now) != tim.end())
      modify(1, 1, n, tim[now], i - 1, now), tim.erase(now);
    else
      tim[now] = i;
  }
  for (it = tim.begin(); it != tim.end(); it++)
    modify(1, 1, n, it->second, n, it->first);
  dfs(1, 1, n);
  for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
  printf("\n");
  return 0;
}