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 
#include <bits/stdc++.h>
using namespace std;
const int n = 1 << 19;
long long par[n * 2], szx[n * 2], szy[n * 2];
int find(int first) {
  int p = par[first];
  if (p == par[p])
    return p;
  else
    return find(par[p]);
}
long long ans = 0;
struct Event {
  pair<int, int> p;
  int pa, pb;
  long long ans0;
  void run() {
    ans0 = ans;
    pa = find(p.first), pb = find(p.second + n);
    if (pa == pb) return;
    ans -= szx[pa] * szy[pa];
    ans -= szx[pb] * szy[pb];
    if (szx[pa] + szy[pa] < szx[pb] + szy[pb]) swap(pa, pb);
    par[pb] = pa;
    szx[pa] += szx[pb];
    szy[pa] += szy[pb];
    ans += szx[pa] * szy[pa];
  }
  void undo() {
    if (pa == pb) return;
    ans -= szx[pa] * szy[pa];
    par[pb] = pb;
    szx[pa] -= szx[pb];
    szy[pa] -= szy[pb];
    ans += szx[pa] * szy[pa];
    ans += szx[pb] * szy[pb];
    assert(ans == ans0);
  }
};
vector<Event> tree[n * 2];
void add(pair<int, int> p, int a, int b, int l = 0, int r = n, int i = 1) {
  if (l >= b || r <= a) return;
  if (l >= a && r <= b) {
    tree[i].push_back({p});
    return;
  }
  int mid = l + r >> 1;
  add(p, a, b, l, mid, i * 2);
  add(p, a, b, mid, r, i * 2 + 1);
}
int q;
void calc(int i) {
  for (Event& e : tree[i]) e.run();
  if (i >= n && i < q + n) cout << ans << ' ';
  if (i < n) {
    calc(i * 2);
    calc(i * 2 + 1);
  }
  reverse(tree[i].begin(), tree[i].end());
  for (Event& e : tree[i]) e.undo();
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 0; i < n * 2; i++) par[i] = i, szx[i] = i < n, szy[i] = i >= n;
  cin >> q;
  map<pair<int, int>, int> m;
  for (int i = 0; i < q; i++) {
    pair<int, int> p;
    cin >> p.first >> p.second;
    if (!m.count(p))
      m[p] = i;
    else {
      add(p, m[p], i);
      m.erase(p);
    }
  }
  for (auto p : m) add(p.first, p.second, q);
  calc(1);
  cout << endl;
}
