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;
const int N = 3e5 + 5, mod = 998244353, Max = 3e5;
template <class o>
inline void qr(o &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + (c ^ 48);
    c = getchar();
  }
  x *= f;
}
template <class o>
void qw(o x) {
  if (x / 10) qw(x / 10);
  putchar(x % 10 + 48);
}
template <class o>
void pr1(o x) {
  if (x < 0) putchar('-'), x = -x;
  qw(x);
  putchar(' ');
}
template <class o>
void pr2(o x) {
  if (x < 0) putchar('-'), x = -x;
  qw(x);
  puts("");
}
inline int ksm(int a, int b = mod - 2) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * ans * a % mod;
  return ans;
}
inline int add(int a, int b) { return a += b, a >= mod ? a - mod : a; }
inline int sub(int a, int b) { return a -= b, a < 0 ? a + mod : a; }
vector<int> t[N << 2];
pair<int, int> e[N], sta[N << 1], cc[N];
int fa[N << 1], dep[N << 1], cx[N << 1], cy[N << 1], top;
long long ans, Ans[N];
void ins(int p, int l, int r, int L, int R, int d) {
  if (L <= l && R >= r) return t[p].push_back(d);
  int mid = l + r >> 1;
  if (L <= mid) ins(p << 1, l, mid, L, R, d);
  if (R > mid) ins(p << 1 | 1, mid + 1, r, L, R, d);
}
int get(int x) { return x == fa[x] ? x : get(fa[x]); }
void merge(int x, int y) {
  int p = get(x), q = get(y);
  if (p == q) return;
  if (dep[q] > dep[p]) swap(p, q);
  ans -= 1ll * cx[p] * cy[p] + 1ll * cx[q] * cy[q];
  fa[q] = p;
  cx[p] += cx[q];
  cy[p] += cy[q];
  sta[++top] = make_pair(q, dep[p] == dep[q]);
  dep[p] += (dep[p] == dep[q]);
  ans += 1ll * cx[p] * cy[p];
}
void dfs(int p, int l, int r) {
  int lst = top;
  for (auto i : t[p]) {
    int x = e[i].first, y = e[i].second;
    merge(x, y);
  }
  int mid = l + r >> 1;
  if (l == r)
    Ans[l] = ans;
  else
    dfs(p << 1, l, mid), dfs(p << 1 | 1, mid + 1, r);
  while (top != lst) {
    int y = sta[top].first, d = sta[top].second, x = fa[y];
    dep[x] -= d;
    ans -= 1ll * cx[x] * cy[x];
    cx[x] -= cx[y];
    cy[x] -= cy[y];
    ans += 1ll * cx[x] * cy[x] + 1ll * cx[y] * cy[y];
    fa[y] = y;
    --top;
  }
}
map<pair<int, int>, int> pos;
int cnt;
void solve() {
  int n;
  qr(n);
  for (int i = 1; i <= n; ++i) {
    int x, y;
    qr(x), qr(y);
    pair<int, int> t = make_pair(x, y + Max);
    if (!pos.count(t)) {
      pos[t] = ++cnt;
      e[cnt] = make_pair(x, y + Max);
      cc[cnt].first = i;
    } else {
      cc[pos[t]].second = i - 1;
      pos.erase(t);
    }
  }
  for (int i = 1; i <= cnt; ++i)
    if (!cc[i].second) cc[i].second = n;
  for (int i = 1; i <= cnt; ++i) ins(1, 1, n, cc[i].first, cc[i].second, i);
  for (int i = 1; i <= Max * 2; ++i)
    fa[i] = i, cx[i] = (i <= Max), cy[i] = 1 - cx[i];
  ans = 0;
  dfs(1, 1, n);
  for (int i = 1; i <= n; ++i) pr1(Ans[i]);
}
int main() {
  solve();
  return 0;
}