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 dsu_save {
  int u, rku, Ru, Cu, v, rkv, Rv, Cv;
  dsu_save() {}
  dsu_save(int _u, int _rku, int _Ru, int _Cu, int _v, int _rkv, int _Rv,
           int _Cv)
      : u(_u),
        rku(_rku),
        Ru(_Ru),
        Cu(_Cu),
        v(_v),
        rkv(_rkv),
        Rv(_Rv),
        Cv(_Cv) {}
};
struct dsu_rollback {
  int p[600005], rk[600005], R[600005], C[600005];
  long long ans;
  stack<dsu_save> op;
  dsu_rollback() {}
  void init() {
    for (int i = 0; i <= 600000; i++) {
      p[i] = i;
      rk[i] = 0;
      if (i > 300000)
        C[i]++;
      else
        R[i]++;
    }
    ans = 0;
  }
  int find(int x) { return (x == p[x]) ? x : find(p[x]); }
  bool uni(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return false;
    ans -= (long long)R[u] * C[u];
    ans -= (long long)R[v] * C[v];
    if (rk[u] < rk[v]) swap(u, v);
    op.push(dsu_save(u, rk[u], R[u], C[u], v, rk[v], R[v], C[v]));
    p[v] = u;
    if (rk[u] == rk[v]) rk[u]++;
    R[u] += R[v];
    C[u] += C[v];
    ans += (long long)R[u] * C[u];
    return true;
  }
  void rollback() {
    if (op.empty()) return;
    dsu_save x = op.top();
    op.pop();
    ans -= (long long)R[x.u] * C[x.u];
    p[x.u] = x.u;
    rk[x.u] = x.rku;
    R[x.u] = x.Ru;
    C[x.u] = x.Cu;
    p[x.v] = x.v;
    rk[x.v] = x.rkv;
    R[x.v] = x.Rv;
    C[x.v] = x.Cv;
    ans += (long long)R[x.u] * C[x.u];
    ans += (long long)R[x.v] * C[x.v];
  }
};
struct query {
  int u, v;
  bool united;
  query() {}
  query(int _u, int _v) : u(_u), v(_v) {}
};
struct QueryTree {
  vector<vector<query> > t;
  dsu_rollback dsu;
  int T;
  QueryTree() {}
  QueryTree(int _T) {
    T = _T;
    dsu.init();
    t.resize(4 * T + 4);
  }
  void add_to_tree(int v, int l, int r, int ul, int ur, query &q) {
    if (ul > ur) return;
    if (l == ul && r == ur) {
      t[v].push_back(q);
      return;
    }
    int mid = (l + r) / 2;
    add_to_tree(2 * v, l, mid, ul, min(ur, mid), q);
    add_to_tree(2 * v + 1, mid + 1, r, max(ul, mid + 1), ur, q);
  }
  void add_query(query q, int l, int r) { add_to_tree(1, 0, T - 1, l, r, q); }
  void dfs(int v, int l, int r, vector<long long> &ans) {
    for (query &q : t[v]) {
      q.united = dsu.uni(q.u, q.v);
    }
    if (l == r)
      ans[l] = dsu.ans;
    else {
      int mid = (l + r) / 2;
      dfs(2 * v, l, mid, ans);
      dfs(2 * v + 1, mid + 1, r, ans);
    }
    for (query q : t[v]) {
      if (q.united) {
        dsu.rollback();
      }
    }
  }
  vector<long long> solve() {
    vector<long long> ans(T);
    dfs(1, 0, T - 1, ans);
    return ans;
  }
} * QT;
int q;
map<pair<int, int>, int> m;
int main() {
  scanf("%d", &q);
  QT = new QueryTree(q);
  for (int i = 0, X, Y; i < q; i++) {
    scanf("%d%d", &X, &Y);
    Y += 300000;
    if (!m.count({X, Y})) {
      m[pair<int, int>(X, Y)] = i;
    } else {
      QT->add_query(query(X, Y), m[pair<int, int>(X, Y)], i - 1);
      m.erase(m.find({X, Y}));
    }
  }
  for (auto C : m) {
    QT->add_query(query(C.first.first, C.first.second), C.second, q - 1);
  }
  vector<long long> ans = QT->solve();
  for (auto x : ans) {
    printf("%lld ", x);
  }
}