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>
const int N_MAX = 600007;
std::map<std::pair<int, int>, int> ext;
long long ans[N_MAX], now;
int fa[N_MAX], siz[N_MAX][2], top;
std::pair<int, int> stk[N_MAX];
int find(int x) {
  while (fa[x] != x) x = fa[x];
  return x;
}
void merge(std::pair<int, int> v) {
  int x = find(v.first), y = find(v.second);
  if (x != y) {
    if (siz[x][0] + siz[x][1] < siz[y][0] + siz[y][1]) std::swap(x, y);
    now -= 1ll * siz[x][0] * siz[x][1] + 1ll * siz[y][0] * siz[y][1];
    siz[x][0] += siz[y][0], siz[x][1] += siz[y][1];
    now += 1ll * siz[x][0] * siz[x][1];
    fa[y] = x, stk[++top] = std::make_pair(x, y);
  }
}
void undoMerge() {
  int x = stk[top].first, y = stk[top].second;
  now -= 1ll * siz[x][0] * siz[x][1];
  siz[x][0] -= siz[y][0], siz[x][1] -= siz[y][1];
  now += 1ll * siz[x][0] * siz[x][1] + 1ll * siz[y][0] * siz[y][1];
  fa[y] = y, --top;
}
static const int T_MAX = 1200007;
std::vector<std::pair<int, int> > op[T_MAX];
void modify(int k, int l, int r, int x, int y, std::pair<int, int> v) {
  if (x <= l && r <= y) {
    op[k].push_back(v);
    return;
  }
  if (x <= ((l + r) >> 1)) modify((k << 1), l, ((l + r) >> 1), x, y, v);
  if (((l + r) >> 1) < y) modify((k << 1 | 1), ((l + r) >> 1) + 1, r, x, y, v);
}
void dfs(int k, int l, int r) {
  int temp = top;
  for (auto v : op[k]) merge(v);
  if (l == r)
    ans[l] = now;
  else
    dfs((k << 1), l, ((l + r) >> 1)), dfs((k << 1 | 1), ((l + r) >> 1) + 1, r);
  while (top > temp) undoMerge();
}
int main() {
  const int n = 3e5;
  int Q;
  scanf("%d", &Q);
  for (int i = 1; i <= Q; ++i) {
    std::pair<int, int> temp;
    scanf("%d%d", &temp.first, &temp.second), temp.second += n;
    if (ext.find(temp) == ext.end())
      ext[temp] = i;
    else
      modify(1, 1, Q, ext[temp], i - 1, temp), ext.erase(temp);
  }
  for (auto i : ext) modify(1, 1, Q, i.second, Q, i.first);
  for (int i = 1; i <= n; ++i) fa[i] = i, siz[i][0] = 1;
  for (int i = n + 1; i <= n + n; ++i) fa[i] = i, siz[i][1] = 1;
  dfs(1, 1, Q);
  for (int i = 1; i <= Q; ++i) printf("%lld ", ans[i]);
  return 0;
}