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>
#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
int IT_MAX = 1 << 17;
const long long MOD = 998244353;
const int INF = 0x3f3f3f3f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
pair<int, int> sz[600050];
int r[600050];
int root(int x) { return (x == r[x]) ? x : root(r[x]); }
vector<pair<int, int>> Vl[2000050];
void init(int st, int en, int S, int E, int n, pair<int, int> v) {
  if (en < S || E < st) return;
  if (st <= S && E <= en) {
    Vl[n].push_back(v);
    return;
  }
  int M = (S + E) / 2;
  init(st, en, S, M, 2 * n, v);
  init(st, en, M + 1, E, 2 * n + 1, v);
}
void printans(int S, int E, int n, long long cur) {
  vector<pair<int, int>> Vr;
  vector<pair<int, pair<int, int>>> Vsz;
  for (auto it : Vl[n]) {
    int a = it.first, b = it.second;
    a = root(a), b = root(b);
    if (a == b) continue;
    if (sz[a].first + sz[a].second > sz[b].first + sz[b].second) swap(a, b);
    cur -= (long long)sz[a].first * sz[a].second;
    cur -= (long long)sz[b].first * sz[b].second;
    Vr.emplace_back(a, r[a]);
    Vsz.emplace_back(b, sz[b]);
    sz[b] =
        pair<int, int>(sz[a].first + sz[b].first, sz[a].second + sz[b].second);
    r[a] = b;
    cur += (long long)sz[b].first * sz[b].second;
  }
  if (S == E)
    printf("%lld ", cur);
  else {
    int M = (S + E) / 2;
    printans(S, M, 2 * n, cur);
    printans(M + 1, E, 2 * n + 1, cur);
  }
  reverse((Vr).begin(), (Vr).end());
  reverse((Vsz).begin(), (Vsz).end());
  for (auto it : Vr) r[it.first] = it.second;
  for (auto it : Vsz) sz[it.first] = it.second;
}
int main() {
  int N, i, j;
  scanf("%d", &N);
  map<pair<int, int>, int> Mx;
  for (i = 1; i <= N; i++) {
    int t1, t2;
    scanf("%d %d", &t1, &t2);
    t2 += 300000;
    if (Mx.count(pair<int, int>(t1, t2))) {
      init(Mx[pair<int, int>(t1, t2)], i - 1, 1, N, 1, pair<int, int>(t1, t2));
      Mx.erase(pair<int, int>(t1, t2));
    } else
      Mx[pair<int, int>(t1, t2)] = i;
  }
  for (auto it : Mx) init(it.second, N, 1, N, 1, it.first);
  for (i = 1; i <= 600000; i++) {
    r[i] = i;
    if (i <= 300000)
      sz[i] = pair<int, int>(1, 0);
    else
      sz[i] = pair<int, int>(0, 1);
  }
  printans(1, N, 1, 0);
  return !printf("\n");
}