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, k;
long long ans[300003];
map<pair<int, int>, int> mp;
vector<int> ask;
vector<pair<pair<int, int>, pair<int, int> > > query;
vector<pair<int, int> > tree[2400003];
void update(int pos, int kir, int kan, int qkir, int qkan, pair<int, int> edg) {
  if (qkir <= kir && kan <= qkan)
    tree[pos].push_back(edg);
  else if (qkan < kir || kan < qkir)
    return;
  else {
    int mid = (kir + kan) / 2;
    update(pos * 2, kir, mid, qkir, qkan, edg);
    update(pos * 2 + 1, mid + 1, kan, qkir, qkan, edg);
  }
}
int par[600003];
int sza[600003], szb[600003];
int parent(int x) { return (par[x] == x) ? x : parent(par[x]); }
long long res = 0;
void tranverse(int pos, int kir, int kan) {
  stack<pair<int, int> > stk;
  int mid = (kir + kan) / 2;
  for (auto i : tree[pos]) {
    int u = i.first, v = i.second;
    u = parent(u);
    v = parent(v);
    if (u != v) {
      if (sza[u] + szb[u] < sza[v] + szb[v]) swap(u, v);
      res -= 1LL * sza[v] * szb[v];
      res -= 1LL * sza[u] * szb[u];
      sza[u] += sza[v];
      szb[u] += szb[v];
      res += 1LL * sza[u] * szb[u];
      par[v] = par[u];
      stk.push({u, v});
    }
  }
  if (kir == kan) {
    ans[kir] = res;
  } else {
    tranverse(pos * 2, kir, mid);
    tranverse(pos * 2 + 1, mid + 1, kan);
  }
  while (stk.size()) {
    int u = stk.top().first, v = stk.top().second;
    res -= 1LL * sza[u] * szb[u];
    sza[u] -= sza[v];
    szb[u] -= szb[v];
    res += 1LL * sza[v] * szb[v];
    res += 1LL * sza[u] * szb[u];
    par[v] = v;
    stk.pop();
  }
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    b += 300000;
    if (mp.find({a, b}) == mp.end())
      mp[{a, b}] = i;
    else {
      query.push_back({{a, b}, {mp[{a, b}], i - 1}});
      mp.erase({a, b});
    }
  }
  for (int i = 1; i <= 300000; i++) {
    par[i] = i;
    par[i + 300000] = i + 300000;
    sza[i] = 1;
    szb[i + 300000] = 1;
  }
  for (auto it : mp)
    query.push_back({{it.first.first, it.first.second}, {it.second, n}});
  for (auto it : query) {
    update(1, 1, n, it.second.first, it.second.second, it.first);
  }
  tranverse(1, 1, n);
  for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], (i == n) ? '\n' : ' ');
}