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;
using pi = pair<int, int>;
using ll = long long;
struct Dsu {
  using pi = pair<int, int>;
  int n;
  vector<int> p;
  vector<int> r;
  vector<int> s;
  vector<pi> histo;
  ll delta = 0;
  Dsu(int _n) {
    n = _n;
    p.resize(n);
    r.resize(n);
    s.resize(n);
    init();
  }
  inline void init() {
    for (int i = 0; i < n; i++) {
      p[i] = i;
      if (i & 1)
        s[i] = 1;
      else
        r[i] = 1;
    }
  }
  inline int find(int x) {
    while (x != p[x]) x = p[x];
    return x;
  }
  inline int join(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return 0;
    if (r[x] < r[y]) swap(x, y);
    histo.emplace_back(x, y);
    delta -= prod(x) + prod(y);
    p[y] = x;
    r[x] += r[y];
    s[x] += s[y];
    delta += prod(x);
    return 1;
  }
  inline int join(pi e) { return join(e.first, e.second); }
  void roll_back() {
    int x, y;
    tie(x, y) = histo.back();
    histo.pop_back();
    delta -= prod(x);
    r[x] -= r[y];
    p[y] = y;
    s[x] -= s[y];
    delta += prod(x) + prod(y);
  }
  inline bool check(int x, int y) { return find(x) == find(y); }
  inline bool check(pi e) { return check(e.first, e.second); }
  ll prod(int x) {
    x = find(x);
    return r[x] * 1ll * s[x];
  }
};
const int N = 1 << 19;
Dsu d(N << 1);
vector<pi> a[N << 1];
ll res[N];
void add(int l, int r, pi& p) {
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l & 1) a[l++].push_back(p);
    if (r & 1) a[--r].push_back(p);
  }
}
void dfs(int u) {
  int did = 0;
  for (auto& p : a[u]) {
    did += d.join(p);
  }
  if (u >= N) {
    res[u - N] = d.delta;
  } else {
    dfs(u << 1);
    dfs(u << 1 | 1);
  }
  while (did--) {
    d.roll_back();
  }
}
void solve() {
  int n;
  cin >> n;
  map<pi, int> pos;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    x = x * 2;
    y = y * 2 + 1;
    pi p = {x, y};
    if (pos.count(p)) {
      add(pos[p], i, p);
      pos.erase(p);
    } else {
      pos[p] = i;
    }
  }
  for (auto& _ : pos) {
    pi p = _.first;
    add(_.second, n, p);
  }
  dfs(1);
  for (int i = 0; i < n; i++) {
    cout << res[i] << ' ';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  return 0;
}