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;
struct node {
  vector<pair<int, int> > upd;
};
const int MAXN = 3e5;
map<pair<int, int>, int> m;
int q, link[2 * MAXN + 5], prvi[2 * MAXN + 5], drugi[2 * MAXN + 5];
node t[(1 << 20) + 5];
long long sad = 0;
void update(int root, int l, int r, int s, int e, pair<int, int> edg) {
  if (l > r || l > e || r < s) return;
  if (l >= s && r <= e) {
    t[root].upd.push_back(edg);
    return;
  }
  int mid = (l + r) / 2;
  update(root * 2, l, mid, s, e, edg);
  update(root * 2 + 1, mid + 1, r, s, e, edg);
}
int find(int first) {
  while (first != link[first]) {
    first = link[first];
  }
  return first;
}
bool same(int first, int second) { return (find(first) == find(second)); }
int vel(int first) { return prvi[first] + drugi[first]; }
void unite(int first, int second) {
  first = find(first);
  second = find(second);
  if (vel(first) < vel(second)) {
    swap(first, second);
  }
  sad -= ((long long)prvi[second] * (long long)drugi[second]);
  sad -= ((long long)prvi[first] * (long long)drugi[first]);
  link[second] = first;
  prvi[first] += prvi[second];
  drugi[first] += drugi[second];
  sad += ((long long)prvi[first] * (long long)drugi[first]);
}
void initstuff() {
  for (int i = 1; i <= MAXN; ++i) {
    link[i] = i;
    prvi[i] = 1;
  }
  for (int i = MAXN + 1; i <= 2 * MAXN; ++i) {
    link[i] = i;
    drugi[i] = 1;
  }
}
void makni(int first, int second) {
  if (vel(first) < vel(second)) {
    swap(first, second);
  }
  sad -= ((long long)prvi[first] * (long long)drugi[first]);
  link[second] = second;
  prvi[first] -= prvi[second];
  drugi[first] -= drugi[second];
  sad += ((long long)prvi[first] * (long long)drugi[first]);
  sad += ((long long)prvi[second] * (long long)drugi[second]);
}
void dfs(int root, int l, int r) {
  if (l > r) return;
  vector<pair<int, int> > prev;
  for (vector<pair<int, int> >::iterator i = t[root].upd.begin();
       i != t[root].upd.end(); ++i) {
    pair<int, int> o = *i;
    int first = o.first, second = o.second;
    if (!same(first, second)) {
      prev.push_back(make_pair(find(first), find(second)));
      unite(first, second);
    }
  }
  if (l != r) {
    int mid = (l + r) / 2;
    dfs(root * 2, l, mid);
    dfs(root * 2 + 1, mid + 1, r);
  } else {
    cout << sad << ' ';
  }
  for (int i = (int)prev.size() - 1; i >= 0; --i) {
    pair<int, int> o = prev[i];
    int first = o.first, second = o.second;
    makni(first, second);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int first, second;
    cin >> first >> second;
    second += MAXN;
    if (m.find(make_pair(first, second)) == m.end()) {
      m[make_pair(first, second)] = i;
    } else {
      update(1, 1, q, m[make_pair(first, second)], i - 1,
             make_pair(first, second));
      m.erase(m.find(make_pair(first, second)));
    }
  }
  for (map<pair<int, int>, int>::iterator i = m.begin(); i != m.end(); ++i) {
    int o = i->second;
    pair<int, int> u = i->first;
    update(1, 1, q, o, q, make_pair(u.first, u.second));
  }
  initstuff();
  dfs(1, 1, q);
  return 0;
}