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 const N = 300000;
int q;
vector<pair<int, int> > s[N << 2];
map<pair<int, int>, int> edtm;
vector<pair<int, int> > p;
long long an[N + 1];
void adsg(pair<int, int> e, int x, int y, int l = 1, int r = q, int id = 1) {
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    s[id].push_back(e);
    return;
  }
  int m = l + r >> 1, a = id << 1, b = a | 1;
  adsg(e, x, y, l, m, a);
  adsg(e, x, y, m + 1, r, b);
}
int pa[N << 1 | 1];
pair<int, int> sz[N << 1 | 1];
stack<pair<int, int> > st;
long long can;
int P(int p) {
  while (pa[p]) p = pa[p];
  return p;
}
void adan(pair<int, int> p) { can += (long long)p.first * p.second; }
void sban(pair<int, int> p) { can -= (long long)p.first * p.second; }
void fn(int l = 1, int r = q, int id = 1) {
  int undc = 0;
  for (auto &t : s[id]) {
    int a = P(t.first), b = P(t.second);
    if (a == b) continue;
    if (sz[a].first + sz[a].second < sz[b].first + sz[b].second) swap(a, b);
    pa[b] = a;
    sban(sz[a]);
    sban(sz[b]);
    sz[a].first += sz[b].first;
    sz[a].second += sz[b].second;
    adan(sz[a]);
    st.push(make_pair(a, b));
    ++undc;
  }
  if (l == r)
    an[l] += can;
  else {
    int m = l + r >> 1, a = id << 1, b = a | 1;
    fn(l, m, a);
    fn(m + 1, r, b);
  }
  while (undc--) {
    int a = st.top().first, b = st.top().second;
    st.pop();
    sban(sz[a]);
    sz[a].first -= sz[b].first;
    sz[a].second -= sz[b].second;
    adan(sz[a]);
    adan(sz[b]);
    pa[b] = 0;
  }
}
int main() {
  scanf("%d", &q);
  for (int i = 0; i < (int)(q); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    b += N;
    pair<int, int> v = make_pair(a, b);
    auto it = edtm.find(v);
    if (it == edtm.end())
      edtm[v] = i + 1;
    else
      adsg(v, it->second, i), edtm.erase(it);
  }
  for (auto it = edtm.begin(); it != edtm.end(); ++it)
    adsg(it->first, it->second, q);
  for (int i = 1; i < (int)(N + 1); ++i) sz[i].first = 1;
  for (int i = N + 1; i < (int)(N << 1 | 1); ++i) sz[i].second = 1;
  fn();
  printf("%lld", an[1]);
  for (int i = 2; i < (int)(q + 1); ++i) printf(" %lld", an[i]);
  printf("\n");
}