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 MX = 300005;
int q, x[MX], y[MX], p[2 * MX], rk[2 * MX];
long long res = 0, first[2 * MX], second[2 * MX];
map<pair<int, int>, vector<int> > mp;
vector<pair<int, int> > st[4 * MX];
vector<int> _x[4 * MX], _y[4 * MX], aux[4 * MX];
int parent(int a) {
  while (a != p[a]) a = p[a];
  return a;
}
void joint(int &x, int &y, int &t) {
  if (x == y) return void(t = -1);
  if (rk[x] < rk[y]) swap(x, y);
  res -= first[x] * second[x] + first[y] * second[y];
  first[x] += first[y], second[x] += second[y];
  res += first[x] * second[x];
  p[y] = x;
  if (rk[x] == rk[y]) rk[x] += t = 1;
}
void undo(int x, int y, int t) {
  if (t == -1) return;
  res -= first[x] * second[x];
  first[x] -= first[y], second[x] -= second[y];
  res += first[x] * second[x] + first[y] * second[y];
  p[y] = y;
  rk[x] -= t;
}
void update(int i, int j, int pos, int l, int r, int x, int y) {
  if (r < i || j < l) return;
  if (l <= i && j <= r) return void(st[pos].emplace_back(x, y));
  int m = (i + j) / 2;
  update(i, m, pos * 2, l, r, x, y);
  update(m + 1, j, pos * 2 + 1, l, r, x, y);
}
void dfs(int i, int j, int pos) {
  aux[pos] = vector<int>(st[pos].size());
  _x[pos] = vector<int>(st[pos].size());
  _y[pos] = vector<int>(st[pos].size());
  for (int i = 0; i < st[pos].size(); i++) {
    _x[pos][i] = parent(st[pos][i].first);
    _y[pos][i] = parent(st[pos][i].second);
    joint(_x[pos][i], _y[pos][i], aux[pos][i]);
  }
  if (i == j) {
    cout << res << " ";
  } else {
    int m = (i + j) / 2;
    dfs(i, m, pos * 2);
    dfs(m + 1, j, pos * 2 + 1);
  }
  for (int i = (int)st[pos].size() - 1; i + 1; i--)
    undo(_x[pos][i], _y[pos][i], aux[pos][i]);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> x[i] >> y[i];
    mp[{x[i], y[i]}].push_back(i);
  }
  for (int i = 0; i < 2 * MX; i++) {
    p[i] = i;
    if (i < MX)
      first[i] = 1;
    else
      second[i] = 1;
  }
  for (map<pair<int, int>, vector<int> >::iterator it = mp.begin();
       it != mp.end(); it++) {
    vector<int> &v = it->second;
    if (v.size() & 1) v.push_back(q + 1);
    for (int j = 0; j < v.size(); j += 2)
      update(1, q, 1, v[j], v[j + 1] - 1, it->first.first,
             it->first.second + MX);
  }
  dfs(1, q, 1);
  cout << '\n';
  return 0;
}