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;
template <class T>
void rd(T &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  x *= f;
}
template <class T>
void pt(T x) {
  if (x < 0) putchar('-'), x = (~x) + 1;
  if (x > 9) pt(x / 10);
  putchar(x % 10 ^ 48);
}
const int N = 3e5 + 5, M = 3e5;
vector<pair<int, int> > tre[N << 2];
map<pair<int, int>, int> Map;
stack<pair<int, int> > Sta;
long long sx[N << 1], sy[N << 1], ans;
int fa[N << 1], n;
int findset(int x) { return !fa[x] ? x : findset(fa[x]); }
void update(int x, int l, int r, int L, int R, pair<int, int> val) {
  if (L <= l && R >= r) {
    tre[x].push_back(val);
    return;
  }
  int mid = (l + r) >> 1;
  if (L <= mid) update((x << 1), l, mid, L, R, val);
  if (R > mid) update((x << 1 | 1), mid + 1, r, L, R, val);
}
void solve(int now, int l, int r) {
  long long tp = ans;
  int tmp = Sta.size();
  for (auto it : tre[now]) {
    int x = findset(it.first), y = findset(it.second + M);
    if (x == y) continue;
    if (sx[x] + sy[x] > sx[y] + sy[y]) swap(x, y);
    ans -= sx[x] * sy[x] + sx[y] * sy[y];
    fa[x] = y;
    sx[y] += sx[x];
    sy[y] += sy[x];
    ans += sx[y] * sy[y];
    Sta.push({x, y});
  }
  if (l != r) {
    int mid = (l + r) >> 1;
    solve((now << 1), l, mid);
    solve((now << 1 | 1), mid + 1, r);
  } else
    pt(ans), puts("");
  ans = tp;
  while (Sta.size() > tmp) {
    int x = Sta.top().first, y = Sta.top().second;
    Sta.pop();
    fa[x] = 0, sx[y] -= sx[x], sy[y] -= sy[x];
  }
}
int main() {
  rd(n);
  for (int i = 1, x, y; i <= n; i++) {
    rd(x), rd(y);
    if (Map[{x, y}]) {
      update(1, 1, n, Map[{x, y}], i - 1, {x, y});
      Map.erase({x, y});
    } else
      Map[{x, y}] = i;
  }
  for (auto it : Map) update(1, 1, n, it.second, n, it.first);
  for (int i = 1; i <= n; i++) fa[i] = 0, sx[i] = 1;
  for (int i = 1; i <= n; i++) fa[i + M] = 0, sy[i + M] = 1;
  solve(1, 1, n);
  return 0;
}