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 = 300000 + 77;
int q;
long long Par[N << 1];
long long A;
long long S[N << 1][2];
vector<pair<int, int> > V[N << 2];
map<long long, int> Prev;
int Find(int x, vector<pair<long long*, long long> >& Op) {
  Op.push_back(make_pair(Par + x, Par[x]));
  return (Par[x] == 0 ? x : Par[x] = Find(Par[x], Op));
}
void Merge(int v, int u, vector<pair<long long*, long long> >& Op) {
  v = Find(v, Op);
  u = Find(u, Op);
  if (v == u) return;
  Op.push_back(make_pair(&A, A));
  A -= S[v][0] * S[v][1] + S[u][0] * S[u][1];
  Op.push_back(make_pair(&S[v][0], S[v][0]));
  S[v][0] += S[u][0];
  Op.push_back(make_pair(&S[v][1], S[v][1]));
  S[v][1] += S[u][1];
  Op.push_back(make_pair(&S[u][0], S[u][0]));
  S[u][0] = 0;
  Op.push_back(make_pair(&S[u][1], S[u][1]));
  S[u][1] = 0;
  Op.push_back(make_pair(Par + u, Par[u]));
  Par[u] = v;
  Op.push_back(make_pair(&A, A));
  A += S[v][0] * S[v][1];
}
void Add(int ql, int qr, pair<int, int> x, int l = 1, int r = q + 1,
         int id = 1) {
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    V[id].push_back(x);
    return;
  }
  int mid = ((l + r) >> 1);
  Add(ql, qr, x, l, mid, id << 1);
  Add(ql, qr, x, mid, r, id << 1 ^ 1);
}
void Get(int l = 1, int r = q + 1, int id = 1) {
  vector<pair<long long*, long long> > Op;
  for (auto x : V[id]) Merge(x.first, x.second, Op);
  if (r - l < 2)
    printf("%lld ", A);
  else {
    int mid = ((l + r) >> 1);
    Get(l, mid, id << 1);
    Get(mid, r, id << 1 ^ 1);
  }
  while (!Op.empty()) {
    auto x = Op.back();
    Op.pop_back();
    *x.first = x.second;
  }
}
int main() {
  for (int i = 1; i < N; ++i) S[i][0] = 1;
  for (int i = N; i < (N << 1); ++i) S[i][1] = 1;
  scanf("%d", &q);
  for (int x, y, i = 1; i <= q; ++i) {
    scanf("%d %d", &x, &y);
    long long t = x * 1ll * N + y;
    if (Prev[t] == 0) {
      Prev[t] = i;
      continue;
    }
    Add(Prev[t], i, make_pair(x + N, y));
    Prev[t] = 0;
  }
  for (auto x : Prev)
    if (x.second > 0)
      Add(x.second, q + 1, make_pair(x.first / N + N, x.first % N));
  Get();
  return 0;
}