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 N = 300005;
int q;
long long tot;
pair<int, int> P[2][N];
vector<pair<int, int> > V[N * 4];
map<pair<int, int>, int> M;
pair<int, int> Find(int w, int v) {
  if (P[w][v].first < 0 || P[w][v].second < 0) return make_pair(w, v);
  return Find(P[w][v].first, P[w][v].second);
}
void Add(int le, int ri, pair<int, int> val, int id = 1, int l = 0, int r = q) {
  if (ri <= l || r <= le) return;
  if (le <= l && r <= ri) return void(V[id].push_back(val));
  Add(le, ri, val, id << 1, l, l + r >> 1);
  Add(le, ri, val, id << 1 ^ 1, l + r >> 1, r);
}
void DFS(int id = 1, int l = 0, int r = q) {
  vector<pair<pair<int, int>, pair<int, int> > > vec;
  for (auto p : V[id]) {
    pair<int, int> a = Find(0, p.first), b = Find(1, p.second);
    if (a != b) {
      tot -= 1LL * P[a.first][a.second].first * P[a.first][a.second].second;
      tot -= 1LL * P[b.first][b.second].first * P[b.first][b.second].second;
      if (P[a.first][a.second].first + P[a.first][a.second].second >
          P[b.first][b.second].first + P[b.first][b.second].second)
        swap(a, b);
      vec.push_back({b, P[b.first][b.second]});
      P[a.first][a.second].first += P[b.first][b.second].first;
      P[a.first][a.second].second += P[b.first][b.second].second;
      P[b.first][b.second] = a;
      tot += 1LL * P[a.first][a.second].first * P[a.first][a.second].second;
    }
  }
  if (r - l < 2)
    printf("%lld ", tot);
  else
    DFS(id << 1, l, l + r >> 1), DFS(id << 1 ^ 1, l + r >> 1, r);
  reverse(vec.begin(), vec.end());
  for (auto op : vec) {
    pair<int, int> b = op.first, a = P[b.first][b.second];
    tot -= 1LL * P[a.first][a.second].first * P[a.first][a.second].second;
    P[b.first][b.second] = op.second;
    P[a.first][a.second].first -= op.second.first;
    P[a.first][a.second].second -= op.second.second;
    tot += 1LL * P[a.first][a.second].first * P[a.first][a.second].second;
    tot += 1LL * P[b.first][b.second].first * P[b.first][b.second].second;
  }
  vec.clear();
}
int main() {
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int X, Y;
    scanf("%d%d", &X, &Y);
    if (M.count({X, Y}))
      Add(M[{X, Y}], i, {X, Y}), M.erase({X, Y});
    else
      M[{X, Y}] = i;
  }
  for (auto X : M) Add(X.second, q, X.first);
  for (int i = 1; i < N; i++) P[0][i] = {-1, 0}, P[1][i] = {0, -1};
  DFS();
  return 0;
}