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;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c *x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug &operator<<(const c &) {
    return *this;
  }
};
struct DSU {
  long long ans = 0;
  int v, rnkv = 1, rv = 0, gv = 0;
  int u, rnku = 1, ru = 0, gu = 0;
  DSU(int v, int rnkv, int rv, int gv, int u, int rnku, int ru, int gu,
      long long ans)
      : v(v),
        rnkv(rnkv),
        rv(rv),
        gv(gv),
        u(u),
        rnku(rnku),
        ru(ru),
        gu(gu),
        ans(ans) {}
};
struct dsu {
  long long ans = 0;
  stack<DSU> oper;
  vector<long long> p, rnk, r, g;
  dsu(int n = 0) {
    p.resize(n);
    r.resize(n);
    g.resize(n);
    rnk.resize(n);
  }
  void make(int v, int f) {
    p[v] = v, rnk[v] = 1;
    r[v] = f, g[v] = !f;
  }
  int par(int v) {
    if (p[v] == v) {
      return v;
    }
    return par(p[v]);
  }
  bool unite(int a, int b) {
    a = par(a), b = par(b);
    if (a == b) return 0;
    if (rnk[a] > rnk[b]) swap(a, b);
    oper.push(DSU(a, rnk[a], r[a], g[a], b, rnk[b], r[b], g[b], ans));
    ans -= r[a] * g[a] + r[b] * g[b];
    ans += (r[a] + r[b]) * (g[a] + g[b]);
    p[a] = b, rnk[b] += rnk[a];
    r[b] += r[a], g[b] += g[a];
    return 1;
  }
  void rick_roll() {
    if (oper.empty()) return;
    auto x = oper.top();
    oper.pop();
    ans = x.ans;
    p[x.v] = x.v, r[x.v] = x.rv, g[x.v] = x.gv, rnk[x.v] = x.rnkv;
    p[x.u] = x.u, r[x.u] = x.ru, g[x.u] = x.gu, rnk[x.u] = x.rnku;
  }
};
struct query {
  int v, u, ok = 0;
  query(int v, int u) : v(v), u(u) {}
};
struct SegmentTree {
  dsu f;
  vector<vector<query> > t;
  SegmentTree(int _t, int n) {
    f = dsu(n);
    t.resize(4 * _t);
  }
  void upd(int v, int vl, int vr, int l, int r, query &x) {
    if (l > r)
      return;
    else if (vl == l && vr == r) {
      t[v].push_back(x);
      return;
    }
    int m = vl + vr >> 1;
    upd(2 * v + 1, vl, m, l, min(r, m), x);
    upd(2 * v + 2, m + 1, vr, max(l, m + 1), r, x);
  }
  void answer(int v, int vl, int vr, vector<long long> &ans) {
    for (auto &x : t[v]) x.ok = f.unite(x.v, x.u);
    if (vl == vr)
      ans[vl] = f.ans;
    else {
      int m = vl + vr >> 1;
      answer(2 * v + 1, vl, m, ans);
      answer(2 * v + 2, m + 1, vr, ans);
    }
    for (auto x : t[v])
      if (x.ok) f.rick_roll();
  }
};
void solve() {
  int n;
  cin >> n;
  map<int, int> a, b;
  vector<pair<int, int> > v(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i].first >> v[i].second;
    ++a[v[i].first], ++b[v[i].second];
  }
  int c = 0;
  for (auto &x : a) x.second = c++;
  for (auto &x : b) x.second = c++;
  int m = c;
  SegmentTree st(n, m);
  for (auto x : a) st.f.make(x.second, 0);
  for (auto x : b) st.f.make(x.second, 1);
  map<pair<int, int>, int> lst;
  for (int i = 0; i < n; ++i) {
    if (lst.count(v[i])) {
      query u(a[v[i].first], b[v[i].second]);
      st.upd(0, 0, n - 1, lst[v[i]], i - 1, u);
      lst.erase(v[i]);
    } else
      lst[v[i]] = i;
  }
  for (auto [a1, b1] : lst) {
    auto [v, u] = a1;
    v = a[v], u = b[u];
    query f(v, u);
    st.upd(0, 0, n - 1, b1, n - 1, f);
  }
  vector<long long> ans(n);
  st.answer(0, 0, n - 1, ans);
  for (auto i : ans) cout << i << " ";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int q = 1;
  while (q--) solve();
}
