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 ll = long long;
const int INF = 1000000000;
const ll LINF = 1001002003004005006ll;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
struct IOSetup {
  IOSetup() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(12);
  }
} iosetup;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++)
    os << v[i] << (i + 1 == (int)v.size() ? "" : " ");
  return os;
}
const int geta = 300005;
struct DynamicConnectivity {
  int V, Q, sz, comp;
  using edge = pair<int, int>;
  vector<vector<edge>> seg;
  vector<pair<pair<int, int>, edge>> pend;
  map<edge, int> cnt, appear;
  vector<int> par, siz;
  vector<pair<ll, ll>> data;
  ll res = 0;
  DynamicConnectivity(int V, int Q) : V(V), Q(Q), comp(V) {
    sz = 1;
    while (sz < Q) sz <<= 1;
    seg.resize(2 * sz);
    par.resize(2 * geta);
    iota(par.begin(), par.end(), 0);
    siz.assign(2 * geta, 1);
    data.resize(2 * geta);
    for (int i = 0; i < (geta); i++) data[i] = {1, 0};
    for (int i = 0; i < (geta); i++) data[i + geta] = {0, 1};
  }
  void insert(int idx, int u, int v) {
    if (u > v) swap(u, v);
    if (cnt[edge(u, v)]++ == 0) appear[edge(u, v)] = idx;
  }
  void erase(int idx, int u, int v) {
    if (u > v) swap(u, v);
    if (--cnt[edge(u, v)] == 0)
      pend.push_back(
          make_pair(make_pair(appear[edge(u, v)], idx), make_pair(u, v)));
  }
  void add(int a, int b, const edge &e, int k = 1, int l = 0, int r = -1) {
    if (r == -1) r = sz;
    if (r <= a or b <= l) return;
    if (a <= l and r <= b) {
      seg[k].push_back(e);
      return;
    }
    add(a, b, e, 2 * k, l, (l + r) / 2);
    add(a, b, e, 2 * k + 1, (l + r) / 2, r);
  }
  void build() {
    for (auto &p : cnt)
      if (p.second > 0)
        pend.emplace_back(make_pair(appear[p.first], sz), p.first);
    for (auto &s : pend) add(s.first.first, s.first.second, s.second);
  }
  struct history {
    int u, v;
    int pre_u_par;
    int pre_v_siz;
    pair<ll, ll> pre_v_data;
    history(int u, int v, int pre_u_par, int pre_v_siz,
            pair<int, int> pre_v_data)
        : u(u),
          v(v),
          pre_u_par(pre_u_par),
          pre_v_siz(pre_v_siz),
          pre_v_data(pre_v_data) {}
  };
  void execute(int k = 1) {
    ll resmemo = res;
    stack<history> st;
    for (auto [u, v] : seg[k]) {
      while (u != par[u]) u = par[u];
      while (v != par[v]) v = par[v];
      if (u == v) continue;
      if (siz[u] > siz[v]) swap(u, v);
      st.push(history(u, v, par[u], siz[v], data[v]));
      par[u] = v;
      siz[v] += siz[u];
      res -= data[u].first * data[u].second + data[v].first * data[v].second;
      data[v] = make_pair(data[u].first + data[v].first,
                          data[u].second + data[v].second);
      res += data[v].first * data[v].second;
    }
    if (k < sz) {
      execute(2 * k);
      execute(2 * k + 1);
    } else if (k - sz < Q) {
      cout << res << (k - sz == Q - 1 ? "\n" : " ");
    }
    while (!st.empty()) {
      auto h = st.top();
      st.pop();
      int u = h.u, v = h.v;
      par[u] = h.pre_u_par;
      siz[v] = h.pre_v_siz;
      data[v] = h.pre_v_data;
    }
    res = resmemo;
  }
};
signed main() {
  int n;
  cin >> n;
  map<pair<int, int>, int> cnt;
  DynamicConnectivity daicon(1, n);
  for (int i = 0; i < (n); i++) {
    int u, v;
    cin >> u >> v;
    if (cnt[make_pair(u, v)] > 0) {
      daicon.erase(i, u, v + geta);
      cnt[make_pair(u, v)]--;
    } else {
      daicon.insert(i, u, v + geta);
      cnt[make_pair(u, v)]++;
    }
  }
  daicon.build();
  daicon.execute();
  return 0;
}