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>
#pragma GCC optimize(2)
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
struct node {
  long long x, y, d;
};
long long n, m, k, res;
stack<node> s;
long long fa[600005], dep[600005], s1[600005], s2[600005];
long long x[600005], y[600005];
vector<long long> e[600005 << 2];
inline long long getf(long long x) {
  while (x != fa[x]) x = fa[x];
  return x;
}
inline void merge(long long x, long long y) {
  if (x == y) return;
  if (dep[x] > dep[y]) swap(x, y);
  res -= s1[x] * s2[x] + s1[y] * s2[y];
  s.push((node){x, y, dep[x] == dep[y]});
  fa[x] = y, dep[y] += s.top().d;
  s1[y] += s1[x], s2[y] += s2[x], res += s1[y] * s2[y];
}
inline void back(long long now) {
  while (s.size() > now) {
    long long x = s.top().x, y = s.top().y;
    dep[y] -= s.top().d;
    fa[x] = x;
    res -= s1[y] * s2[y];
    s1[y] -= s1[x], s2[y] -= s2[x];
    res += s1[x] * s2[x] + s1[y] * s2[y];
    s.pop();
  }
}
void ins(long long p, long long l, long long r, long long nl, long long nr,
         long long x) {
  if (l >= nl && r <= nr) return e[p].push_back(x);
  long long mid = l + r >> 1;
  if (nl <= mid) ins(p << 1, l, mid, nl, nr, x);
  if (nr > mid) ins(p << 1 | 1, mid + 1, r, nl, nr, x);
}
void dfs(long long p, long long l, long long r) {
  long long now = s.size();
  for (long long u : e[p]) merge(getf(x[u]), getf(y[u]));
  if (l == r)
    printf("%lld ", res);
  else {
    long long mid = l + r >> 1;
    dfs(p << 1, l, mid), dfs(p << 1 | 1, mid + 1, r);
  }
  back(now);
}
map<long long, long long> mp[300005];
long long st[600005], ed[600005], cnt;
signed main() {
  m = read();
  n = 300000;
  for (register long long i = (1); i <= (n * 2); ++i)
    fa[i] = i, s1[i] = (i <= n), s2[i] = (i > n);
  for (register long long i = (1); i <= (m); ++i) {
    long long x = read(), y = read() + n;
    if (mp[x].find(y) != mp[x].end()) {
      ed[mp[x][y]] = i - 1;
      mp[x].erase(y);
    } else {
      mp[x][y] = ++cnt;
      ::x[cnt] = x, ::y[cnt] = y, st[cnt] = i, ed[cnt] = m;
    }
  }
  for (register long long i = (1); i <= (cnt); ++i)
    ins(1, 1, m, st[i], ed[i], i);
  dfs(1, 1, m);
  return 0;
}
