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;
namespace FGF {
int n, m;
const int N = 3e5 + 5;
map<pair<int, int>, int> mp;
vector<pair<int, int> > g[N << 2];
int fa[N << 1], siz1[N << 1], siz2[N << 1], tp;
struct Node {
  int u, siz1, siz2;
} st[N << 2];
void updat(int ro, int l, int r, int L, int R, pair<int, int> x) {
  if (L <= l && r <= R) {
    g[ro].push_back(x);
    return;
  }
  if (L <= ((l + r) >> 1)) updat(ro << 1, l, ((l + r) >> 1), L, R, x);
  if (R > ((l + r) >> 1)) updat(ro << 1 | 1, ((l + r) >> 1) + 1, r, L, R, x);
}
int find(int x) {
  while (x != fa[x]) x = fa[x];
  return x;
}
void merge(int u, int v, long long &ans) {
  u = find(u), v = find(v);
  if (u == v) return;
  if (siz1[u] + siz2[u] > siz1[v] + siz2[v]) swap(u, v);
  st[++tp] = {u, siz1[u], siz2[u]};
  ans -= (1ll * siz1[u] * siz2[u] + 1ll * siz2[v] * siz1[v]);
  fa[u] = v, siz2[v] += siz2[u], siz1[v] += siz1[u];
  ans += 1ll * siz2[v] * siz1[v];
}
void solve(int ro, int l, int r, long long ans) {
  int tmp = tp;
  for (auto v : g[ro]) merge(v.first, v.second, ans);
  if (l == r)
    printf("%lld ", ans);
  else
    solve(ro << 1, l, ((l + r) >> 1), ans),
        solve(ro << 1 | 1, ((l + r) >> 1) + 1, r, ans);
  while (tp > tmp) {
    int u = st[tp].u, s1 = st[tp].siz1, s2 = st[tp--].siz2;
    siz1[fa[u]] -= s1, siz2[fa[u]] -= s2, fa[u] = u;
  }
}
void work() {
  scanf("%d", &n);
  for (int i = 1, u, v; i <= n; i++) {
    scanf("%d%d", &u, &v);
    if (mp.find(make_pair(u, v + 3e5)) == mp.end())
      mp[make_pair(u, v + 3e5)] = i;
    else
      updat(1, 1, n, mp[make_pair(u, v + 3e5)], i - 1, make_pair(u, v + 3e5)),
          mp.erase(make_pair(u, v + 3e5));
  }
  for (auto v : mp) updat(1, 1, n, v.second, n, v.first);
  for (int i = 1; i <= 3e5; i++) fa[i] = i, siz1[i] = 1;
  for (int i = 3e5 + 1; i <= 6e5; i++) fa[i] = i, siz2[i] = 1;
  solve(1, 1, n, 0);
}
}  // namespace FGF
int main() {
  FGF::work();
  return 0;
}