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;
long long M = 300001;
long long parent[600002];
long long rnk[600002];
long long szx[600002];
long long szy[600002];
long long anss, q;
map<pair<long long, long long>, long long> pp;
set<pair<pair<long long, long long>, long long> > ppp;
vector<pair<long long, long long> > zpn;
vector<pair<long long, long long> > zpk;
long long xx[600002], yy[600002];
void make_set(int v) {
  if (v <= M) {
    szx[v] = 1;
  } else {
    szy[v] = 1;
  }
  parent[v] = v;
  rnk[v] = 0;
}
int find_set(int v) {
  if (v == parent[v]) return v;
  return find_set(parent[v]);
}
vector<pair<long long, pair<long long, long long> > > izm;
void union_sets(int a, int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (rnk[a] < rnk[b]) swap(a, b);
    parent[b] = a;
    anss = anss - szx[b] * szy[b] - szx[a] * szy[a];
    izm.push_back({b, {szx[a], szy[a]}});
    szx[a] += szx[b];
    szy[a] += szy[b];
    anss += szx[a] * szy[a];
    if (rnk[a] == rnk[b]) ++rnk[a];
  }
}
vector<long long> ans;
long long last;
long long vh[600000];
void bl(long long l, long long r) {
  if (r - l == 1) {
    ans[l] = anss;
    if (vh[l]) {
      long long kek1 = find_set(xx[l]), kek2 = find_set(yy[l] + M);
      if (kek1 != kek2) {
        ans[l] += szx[kek1] * szy[kek2] + szx[kek2] * szy[kek1];
      }
    }
    return;
  }
  long long L = 0, R = zpn.size();
  while (R - L > 1) {
    long long mm = (R + L) / 2;
    if (zpk[mm].first < r) {
      L = mm;
    } else {
      R = mm;
    }
  }
  long long oldans = anss, last = izm.size();
  for (int i = L; i > -1 && zpk[i].first >= (l + r) / 2; i--) {
    if (zpk[i].second <= l) {
      long long id = zpk[i].second;
      union_sets(xx[id], yy[id] + M);
    }
  }
  if (r != l + 1) bl(l, (l + r) / 2);
  anss = oldans;
  long long rrrr = izm.size() - 1;
  for (int i = rrrr; i >= last; i--) {
    long long bb = izm[i].first, t1 = izm[i].second.first,
              t2 = izm[i].second.second;
    szx[parent[bb]] = t1;
    szy[parent[bb]] = t2;
    if (rnk[bb] == rnk[parent[bb]] - 1) {
      rnk[parent[bb]]--;
    }
    parent[bb] = bb;
    izm.pop_back();
  }
  L = 0, R = zpn.size();
  while (R - L > 1) {
    long long mm = (R + L) / 2;
    if (zpn[mm].first >= l) {
      R = mm;
    } else {
      L = mm;
    }
  }
  oldans = anss;
  last = izm.size();
  for (int i = R; i < zpn.size() && zpn[i].first < (l + r) / 2; i++) {
    if (zpn[i].second >= r) {
      long long id = zpn[i].first;
      union_sets(xx[id], yy[id] + M);
    }
  }
  if (l + 1 != r)
    bl((l + r) / 2, r);
  else
    ans[l] = anss;
  anss = oldans;
  rrrr = izm.size() - 1;
  for (int i = rrrr; i >= last; i--) {
    long long bb = izm[i].first, t1 = izm[i].second.first,
              t2 = izm[i].second.second;
    szx[parent[bb]] = t1;
    szy[parent[bb]] = t2;
    if (rnk[bb] == rnk[parent[bb]] - 1) {
      rnk[parent[bb]]--;
    }
    parent[bb] = bb;
    izm.pop_back();
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> q;
  ans.resize(q);
  for (int i = 0; i < 2 * M; i++) {
    make_set(i);
  }
  for (int i = 0; i < q; i++) {
    cin >> xx[i] >> yy[i];
    if (pp.count({xx[i], yy[i]})) {
      vh[pp[{xx[i], yy[i]}]] = 1;
      zpk.push_back({i, pp[{xx[i], yy[i]}]});
      zpn.push_back({pp[{xx[i], yy[i]}], i});
      ppp.erase({{xx[i], yy[i]}, pp[{xx[i], yy[i]}]});
      pp.erase({xx[i], yy[i]});
    } else {
      pp[{xx[i], yy[i]}] = i;
      ppp.insert({{xx[i], yy[i]}, i});
    }
  }
  for (auto i : ppp) {
    vh[i.second] = 1;
    zpn.push_back({i.second, q});
    zpk.push_back({q, i.second});
  }
  sort(zpk.begin(), zpk.end());
  sort(zpn.begin(), zpn.end());
  if (zpn[0].second == q) {
    union_sets(xx[0], yy[0] + M);
  }
  bl(0, q);
  for (auto t : ans) {
    cout << t << " ";
  }
}