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 = 6 * 100010;
const int OFFSET = 3 * 100000;
map<pair<int, int>, int> mf;
int q, dsu[N], sz1[N], sz2[N];
pair<int, int> E[N];
long long ans = 0;
vector<int> seg[4 * N];
struct state {
  int v, u, f1, f2;
  state() {}
  state(int _v, int _u, int _f1, int _f2) {
    v = _v, u = _u, f1 = _f1, f2 = _f2;
  }
};
stack<state> rlb;
int find(int u) { return dsu[u] == u ? u : find(dsu[u]); }
void rollback() {
  state r = rlb.top();
  rlb.pop();
  ans -= 1ll * sz1[r.u] * sz2[r.u];
  dsu[r.v] = r.v;
  sz1[r.u] = r.f1;
  sz2[r.u] = r.f2;
  ans += 1ll * sz1[r.u] * sz2[r.u];
  ans += 1ll * sz1[r.v] * sz2[r.v];
}
void uni(int u, int v) {
  if (find(u) == find(v)) return;
  u = find(u);
  v = find(v);
  int szu = sz1[u] + sz2[u];
  int szv = sz1[v] + sz2[v];
  if (szu < szv) swap(u, v);
  ans -= 1ll * sz1[u] * sz2[u];
  ans -= 1ll * sz1[v] * sz2[v];
  rlb.push(state(v, u, sz1[u], sz2[u]));
  sz1[u] += sz1[v];
  sz2[u] += sz2[v];
  ans += 1ll * sz1[u] * sz2[u];
  dsu[v] = u;
}
int l, r, val;
void insert(int n, int s, int e) {
  if (s > r || e < l) return;
  if (s >= l && e <= r) {
    seg[n].push_back(val);
    return;
  }
  insert(2 * n, s, (s + e) / 2);
  insert(2 * n + 1, (s + e) / 2 + 1, e);
}
void dfs(int n, int s, int e) {
  int cur = rlb.size();
  for (auto cur : seg[n]) uni(E[cur].first, E[cur].second);
  if (s == e) {
    printf("%lld\n", ans);
  }
  if (s != e) {
    dfs(2 * n, s, (s + e) / 2);
    dfs(2 * n + 1, (s + e) / 2 + 1, e);
  }
  while (rlb.size() > cur) rollback();
}
int main() {
  cin >> q;
  for (int i = 1; i <= OFFSET; ++i) dsu[i] = i, sz1[i] = 1;
  for (int i = 1 + OFFSET; i <= 2 * OFFSET; ++i) dsu[i] = i, sz2[i] = 1;
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d", &E[i].first, &E[i].second);
    E[i].second += OFFSET;
    if (mf.find(E[i]) != mf.end()) {
      l = mf[E[i]];
      r = i - 1;
      val = l;
      insert(1, 1, q);
      mf.erase(E[i]);
    } else {
      mf[E[i]] = i;
    }
  }
  for (auto v : mf) {
    l = v.second;
    r = q;
    val = l;
    insert(1, 1, q);
  }
  dfs(1, 1, q);
  return 0;
}
