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;
int N;
int TT[600005], R[600005];
int Sz[2][600005];
const int MAXCOORD = 300000;
long long ans;
map<pair<int, int>, int> X;
pair<pair<int, int>, pair<int, int> > V[600005];
vector<pair<int, int> > Tree[300005 * 4];
int Total[300005];
void addInTree(int K, int L, int R, int x, int y, pair<int, int> val) {
  if (L > R || L > y || R < x) return;
  if (L >= x && R <= y) {
    Tree[K].push_back(val);
    return;
  }
  addInTree(K * 2, L, (L + R) / 2, x, y, val);
  addInTree(K * 2 + 1, (L + R) / 2 + 1, R, x, y, val);
}
void Read() {
  scanf("%d", &N);
  for (int i = 1; i <= 2 * MAXCOORD; i++) TT[i] = i;
  for (int i = 1; i <= MAXCOORD; i++) Sz[0][i] = 1;
  for (int i = 1; i <= MAXCOORD; i++) Sz[1][i + MAXCOORD] = 1;
  for (int i = 1; i <= N; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (X.find(make_pair(x, y)) != X.end()) {
      int left = X[make_pair(x, y)];
      int right = i - 1;
      addInTree(1, 1, N, left, right, make_pair(x, y + MAXCOORD));
      X.erase(make_pair(x, y));
    } else {
      X[make_pair(x, y)] = i;
    }
    Total[i] = X.size();
  }
  map<pair<int, int>, int>::iterator it;
  for (it = X.begin(); it != X.end(); it++) {
    addInTree(1, 1, N, it->second, N,
              make_pair(it->first.first, it->first.second + MAXCOORD));
  }
}
int Father(int x) {
  while (x != TT[x]) x = TT[x];
  return x;
}
void DFS(int node, int L, int Ri) {
  vector<pair<pair<int, int>, pair<int, int> > > Old;
  for (int i = 0; i < Tree[node].size(); i++) {
    pair<int, int> edge = Tree[node][i];
    int f0 = Father(edge.first), f1 = Father(edge.second);
    Old.push_back(
        make_pair(make_pair(Sz[0][f0], Sz[1][f0]), make_pair(R[f0], f0)));
    Old.push_back(
        make_pair(make_pair(Sz[0][f1], Sz[1][f1]), make_pair(R[f1], f1)));
  }
  long long oldAns = ans;
  for (int i = 0; i < Tree[node].size(); i++) {
    pair<int, int> edge = Tree[node][i];
    int f0 = Father(edge.first), f1 = Father(edge.second);
    if (f0 == f1) continue;
    if (R[f0] < R[f1]) {
      TT[f0] = f1;
      ans -= 1LL * Sz[0][f0] * Sz[1][f0] + 1LL * Sz[0][f1] * Sz[1][f1];
      Sz[0][f1] += Sz[0][f0];
      Sz[1][f1] += Sz[1][f0];
      ans += 1LL * Sz[0][f1] * Sz[1][f1];
    } else {
      TT[f1] = f0;
      ans -= 1LL * Sz[0][f0] * Sz[1][f0] + 1LL * Sz[0][f1] * Sz[1][f1];
      Sz[0][f0] += Sz[0][f1];
      Sz[1][f0] += Sz[1][f1];
      ans += 1LL * Sz[0][f0] * Sz[1][f0];
    }
    if (R[f0] == R[f1]) ++R[f0];
  }
  if (L != Ri) {
    DFS(node * 2, L, (L + Ri) / 2);
    DFS(node * 2 + 1, (L + Ri) / 2 + 1, Ri);
  } else {
    printf("%I64d ", ans);
  }
  for (int i = 0; i < Old.size(); i++) {
    pair<pair<int, int>, pair<int, int> > aux = Old[i];
    Sz[0][aux.second.second] = aux.first.first;
    Sz[1][aux.second.second] = aux.first.second;
    R[aux.second.second] = aux.second.first;
    TT[aux.second.second] = aux.second.second;
  }
  ans = oldAns;
}
int main() {
  Read();
  DFS(1, 1, N);
  return 0;
}