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;
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
const double eps = 1e-9;
const int maxn = 6e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N, M, K;
map<pair<int, int>, int> P;
int fa[maxn];
long long size1[maxn], size2[maxn];
int dep[maxn];
void init() {
  for (int i = 0; i < maxn; i++) {
    fa[i] = i;
    if (i > 3e5)
      size2[i] = 1;
    else
      size1[i] = 1;
    dep[i] = 0;
  }
}
struct Edge {
  pair<int, int> to;
  int next;
} edge[maxn * 20];
int tot;
void add(int& t, pair<int, int> w) {
  edge[tot].to = w;
  edge[tot].next = t;
  t = tot++;
}
struct Tree {
  int l, r;
  int head;
} tree[maxn << 2];
void Build(int t, int l, int r) {
  tree[t].l = l;
  tree[t].r = r;
  tree[t].head = -1;
  if (l == r) return;
  int m = l + r >> 1;
  Build(t << 1, l, m);
  Build(t << 1 | 1, m + 1, r);
}
void add(int t, int l, int r, pair<int, int> w) {
  if (l <= tree[t].l && tree[t].r <= r) {
    add(tree[t].head, w);
    return;
  }
  int m = tree[t].l + tree[t].r >> 1;
  if (r <= m)
    add(t << 1, l, r, w);
  else if (l > m)
    add(t << 1 | 1, l, r, w);
  else {
    add(t << 1, l, m, w);
    add(t << 1 | 1, m + 1, r, w);
  }
}
int Stack[maxn], top;
int find(int x) {
  while (fa[x] != x) x = fa[x];
  return x;
}
long long ans;
void rewind(int t) {
  while (top > t) {
    int x = Stack[--top];
    dep[fa[x]] -= dep[x] + 1;
    ans -= 1LL * size1[fa[x]] * size2[fa[x]];
    size1[fa[x]] -= size1[x];
    size2[fa[x]] -= size2[x];
    ans += 1LL * size1[fa[x]] * size2[fa[x]];
    ans += 1LL * size1[x] * size2[x];
    fa[x] = x;
  }
}
void dfs(int t) {
  int now = top;
  for (int i = tree[t].head; ~i; i = edge[i].next) {
    pair<int, int> t = edge[i].to;
    t.first = find(t.first);
    t.second = find(t.second);
    if (t.first == t.second) continue;
    if (dep[t.first] > dep[t.second]) swap(t.first, t.second);
    Stack[top++] = t.first;
    fa[t.first] = t.second;
    dep[t.second] += dep[t.first] + 1;
    ans -= 1LL * size1[t.first] * size2[t.first];
    ans -= size1[t.second] * size2[t.second];
    size1[t.second] += size1[t.first];
    size2[t.second] += size2[t.first];
    ans += 1LL * size1[t.second] * size2[t.second];
  }
  if (tree[t].l == tree[t].r) {
    printf("%lld ", ans);
  } else {
    dfs(t << 1);
    dfs(t << 1 | 1);
  }
  rewind(now);
}
int main() {
  scanf("%d", &N);
  init();
  Build(1, 1, N);
  for (int i = 1; i <= N; i++) {
    pair<int, int> p;
    p.first = read(), p.second = read() + 3e5;
    if (P[p]) {
      add(1, P[p], i - 1, p);
      P[p] = 0;
    } else
      P[p] = i;
  }
  for (map<pair<int, int>, int>::iterator it = P.begin(); it != P.end(); it++)
    if ((*it).second) add(1, (*it).second, N, (*it).first);
  dfs(1);
  return 0;
}
