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 long long MOD = 1e9 + 7;
const int N = 6e5 + 10;
int fa[N], sz1[N], sz2[N], q, x, y, top = 0;
int dsu1[N], dsu2[N];
map<int, int> mp[N >> 1];
vector<pair<int, int> > e[N << 1];
void ins(int from, int to, pair<int, int> p, int id = 1, int l = 1, int r = q) {
  if (from <= l && to >= r) {
    e[id].push_back(p);
    return;
  }
  int mid = l + r >> 1;
  if (mid >= from) ins(from, to, p, id << 1, l, mid);
  if (mid < to) ins(from, to, p, id << 1 | 1, mid + 1, r);
}
int find(int x) { return x == fa[x] ? x : find(fa[x]); }
void dfs(int id = 1, int l = 1, int r = q, long long ans = 0) {
  int now = top;
  for (auto p : e[id]) {
    int x = find(p.first), y = find(p.second);
    if (x == y) continue;
    if (sz1[x] + sz2[x] < sz1[y] + sz2[y]) swap(x, y);
    ans = ans + 1ll * sz1[x] * sz2[y] + 1ll * sz1[y] * sz2[x];
    sz1[x] += sz1[y];
    sz2[x] += sz2[y];
    dsu1[++top] = x, dsu2[top] = y;
    fa[y] = x;
  }
  if (l == r) {
    printf("%lld ", ans);
    return;
  }
  int mid = l + r >> 1;
  dfs(id << 1, l, mid, ans);
  dfs(id << 1 | 1, mid + 1, r, ans);
  for (; top > now; --top) {
    sz1[dsu1[top]] -= sz1[dsu2[top]], sz2[dsu1[top]] -= sz2[dsu2[top]];
    fa[dsu2[top]] = dsu2[top];
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  memset(sz1, 0, sizeof sz1);
  memset(sz2, 0, sizeof sz2);
  for (int i = (1); i <= (6e5); ++i) fa[i] = i, (i <= 3e5 ? sz1 : sz2)[i] = 1;
  scanf("%d", &q);
  for (int i = (1); i <= (q); ++i) {
    scanf("%d%d", &x, &y);
    y += 3e5;
    if (mp[x][y])
      ins(mp[x][y], i - 1, make_pair(x, y)), mp[x][y] = 0;
    else
      mp[x][y] = i;
  }
  for (int i = (1); i <= (3e5); ++i)
    for (auto u : mp[i])
      if (u.second) ins(u.second, q, make_pair(i, u.first));
  dfs();
  return 0;
}
