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 long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
const int maxn = 6e5 + 10;
int Q, num, Max;
int fa[maxn], top, cnt1[maxn], cnt2[maxn];
struct node {
  int x, c1, c2;
} sta[maxn];
struct Edge {
  int from, to;
} e[maxn];
map<pair<int, int>, int> mp;
vector<int> V[maxn];
int get(int x) {
  while (fa[x] != x) x = fa[x];
  return x;
}
void merge(int x, int y) {
  int fx = get(x), fy = get(y);
  if (cnt1[fx] + cnt2[fx] > cnt1[fy] + cnt2[fy]) swap(fx, fy);
  sta[++top] = (node){fx, cnt1[fx], cnt2[fx]};
  fa[fx] = fy;
  cnt1[fy] += cnt1[fx], cnt2[fy] += cnt2[fx];
}
struct Seg_Tree {
  vector<int> c[maxn << 2];
  void insert(int L, int R, int l, int r, int p, int x) {
    if (L <= l && R >= r) {
      c[p].push_back(x);
      return;
    }
    int mid = (l + r) >> 1;
    if (mid >= L) insert(L, R, l, mid, p << 1, x);
    if (mid < R) insert(L, R, mid + 1, r, p << 1 | 1, x);
  }
  void solve(int l, int r, int p, long long Ans) {
    int Nowtop = top;
    for (int i = 0; i < c[p].size(); ++i) {
      int x = e[c[p][i]].from, y = e[c[p][i]].to;
      int fx = get(x), fy = get(y);
      if (fx != fy) {
        Ans -= (long long)cnt1[fx] * cnt2[fx] + (long long)cnt1[fy] * cnt2[fy];
        merge(x, y);
        Ans += (long long)cnt1[get(y)] * cnt2[get(y)];
      }
    }
    if (l == r)
      printf("%lld ", Ans);
    else {
      int mid = (l + r) >> 1;
      solve(l, mid, p << 1, Ans);
      solve(mid + 1, r, p << 1 | 1, Ans);
    }
    while (top > Nowtop) {
      cnt1[fa[sta[top].x]] -= sta[top].c1;
      cnt2[fa[sta[top].x]] -= sta[top].c2;
      fa[sta[top].x] = sta[top].x;
      top--;
    }
  }
} T;
int en[maxn];
int main() {
  Q = read();
  Max = 3e5;
  int tim = 0;
  for (int i = 1; i <= Q; ++i) {
    int u = read(), v = read();
    tim++;
    v += Max;
    pair<int, int> Now = make_pair(u, v);
    if (mp.find(Now) != mp.end())
      V[mp[Now]].push_back(tim), en[mp[Now]] = 1, mp.erase(Now);
    else {
      e[++num] = (Edge){u, v};
      V[num].push_back(tim - 1);
      mp[Now] = num;
    }
  }
  for (int i = 1; i <= num; ++i) {
    if (!en[i]) V[i].push_back(tim + 1);
    for (int j = 1; j < V[i].size(); ++j)
      if (V[i][j - 1] + 1 <= V[i][j] - 1)
        T.insert(V[i][j - 1] + 1, V[i][j] - 1, 1, tim, 1, i);
  }
  Max *= 2;
  for (int i = 1; i <= Max / 2; ++i) fa[i] = i, cnt1[i] = 1;
  for (int i = Max / 2 + 1; i <= Max; ++i) fa[i] = i, cnt2[i] = 1;
  T.solve(1, tim, 1, 0);
  puts("");
  return 0;
}