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;
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? -x : x; }
inline double Fmax(double x, double y) { return x > y ? x : y; }
inline double Fmin(double x, double y) { return x < y ? x : y; }
inline double Fabs(double x) { return x < 0 ? -x : x; }
const int M = 3e5;
map<pair<long long, long long>, int> t;
int n;
long long ans;
struct node {
  int l, r;
  vector<pair<long long, long long> > e;
} tree[M * 4 + 20];
struct dsu {
  int f;
  pair<long long, long long> sz;
} d[M * 2 + 10];
struct nodee {
  int x, y;
  long long sum;
  pair<long long, long long> szx, szy;
};
deque<nodee> q;
void build(int id, int l, int r) {
  tree[id].l = l;
  tree[id].r = r;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid + 1, r);
}
void change(int id, int l, int r, pair<long long, long long> x) {
  if (l <= tree[id].l && tree[id].r <= r) {
    tree[id].e.push_back(x);
    return;
  }
  int mid = (tree[id].l + tree[id].r) / 2;
  if (l <= mid) {
    change(id * 2, l, r, x);
  }
  if (mid + 1 <= r) {
    change(id * 2 + 1, l, r, x);
  }
}
pair<long long, long long> tmp[M + 5];
int getfa(int x) { return (x == d[x].f) ? x : getfa(d[x].f); }
inline bool merge(int x, int y) {
  x = getfa(x);
  y = getfa(y);
  if (x == y) return false;
  q.push_front((nodee){x, y, ans, d[x].sz, d[y].sz});
  ans -= 1ll * d[x].sz.first * d[x].sz.second +
         1ll * d[y].sz.first * d[y].sz.second;
  if (d[x].sz.first + d[x].sz.second > d[y].sz.first + d[y].sz.second)
    swap(x, y);
  d[y].sz.first += d[x].sz.first;
  d[y].sz.second += d[x].sz.second;
  d[x].f = y;
  ans += 1ll * d[y].sz.first * d[y].sz.second;
  return true;
}
inline void ex() {
  nodee t = q.front();
  d[t.x] = (dsu){t.x, t.szx};
  d[t.y] = (dsu){t.y, t.szy};
  ans = t.sum;
  q.pop_front();
}
void dfs(int id) {
  int tot = 0;
  for (int i = 0; i < (int)tree[id].e.size(); i++) {
    tot += merge(tree[id].e[i].first, tree[id].e[i].second + M);
  }
  if (tree[id].l == tree[id].r) {
    printf("%lld ", ans);
  } else {
    dfs(id * 2);
    dfs(id * 2 + 1);
  }
  while (tot--) {
    ex();
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= M; i++) {
    d[i] = (dsu){i, pair<long long, long long>(1, 0)};
    d[i + M] = (dsu){i + M, pair<long long, long long>(0, 1)};
  }
  build(1, 1, n);
  for (int i = 1, x, y; i <= n; i++) {
    scanf("%d%d", &x, &y);
    int p = t[pair<long long, long long>(x, y)];
    tmp[i] = pair<long long, long long>(x, y);
    if (p != 0) {
      change(1, p, i - 1, pair<long long, long long>(x, y));
      t[pair<long long, long long>(x, y)] = 0;
    } else {
      t[pair<long long, long long>(x, y)] = i;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (t[tmp[i]] != 0) {
      change(1, t[tmp[i]], n, tmp[i]);
      t[tmp[i]] = 0;
    }
  }
  dfs(1);
  return 0;
}