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 MAXN = 300000;
int sub[2 * MAXN + 5][2];
int par[2 * MAXN + 5];
int getRoot(int a) {
  while (par[a] > 0) {
    a = par[a];
  }
  return a;
}
long long int ans = 0;
void dsu(int a, int b) {
  int x0 = sub[a][0] + sub[b][0];
  int x1 = sub[a][1] + sub[b][1];
  ans -= sub[a][0] * 1ll * sub[a][1] + sub[b][0] * 1ll * sub[b][1];
  ans += x0 * 1ll * x1;
  if (sub[a][0] + sub[a][1] < sub[b][0] + sub[b][1]) {
    sub[b][0] = x0;
    sub[b][1] = x1;
    par[a] = b;
  } else {
    sub[a][0] = x0;
    sub[a][1] = x1;
    par[b] = a;
  }
}
void removeDSU(int a, int b) {
  if (sub[a][0] + sub[a][1] < sub[b][0] + sub[b][1]) {
    sub[b][0] -= sub[a][0];
    sub[b][1] -= sub[a][1];
    par[a] = -1;
  } else {
    sub[a][0] -= sub[b][0];
    sub[a][1] -= sub[b][1];
    par[b] = -1;
  }
  ans -= (sub[a][0] + sub[b][0]) * 1ll * (sub[a][1] + sub[b][1]);
  ans += sub[a][0] * 1ll * sub[a][1] + sub[b][0] * 1ll * sub[b][1];
}
vector<pair<int, int> > st[8 * MAXN];
void addEdge(int id, int l, int r, int u, int v, int x, int y) {
  if (v < l || r < u) return;
  if (u <= l && r <= v) {
    st[id].push_back(pair<int, int>(x, y));
    return;
  }
  int mid = (l + r) / 2;
  addEdge(id * 2, l, mid, u, v, x, y);
  addEdge(id * 2 + 1, mid + 1, r, u, v, x, y);
}
unordered_map<int, int> prevApp[MAXN + 4];
long long int res[MAXN + 5];
void dfs(int id, int l, int r) {
  vector<pair<int, int> > operations;
  for (auto i : st[id]) {
    int m = getRoot(i.first);
    int n = getRoot(i.second);
    if (m == n) {
      continue;
    }
    operations.push_back(pair<int, int>(m, n));
    dsu(m, n);
  }
  int mid = (l + r) / 2;
  if (l == r) {
    res[l] = ans;
  } else {
    dfs(id * 2, l, mid);
    dfs(id * 2 + 1, mid + 1, r);
  }
  reverse(operations.begin(), operations.end());
  for (auto i : operations) {
    removeDSU(i.first, i.second);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(NULL);
  int q;
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int x, y;
    cin >> x >> y;
    if (prevApp[x][y] == 0) {
      prevApp[x][y] = i;
    } else {
      addEdge(1, 1, q, prevApp[x][y], i - 1, x, y + MAXN);
      prevApp[x][y] = 0;
    }
  }
  for (int i = 1; i <= MAXN; i++) {
    for (auto j : prevApp[i]) {
      if (j.second > 0) {
        addEdge(1, 1, q, j.second, q, i, j.first + MAXN);
      }
    }
  }
  memset(par, -1, sizeof(par));
  for (int i = 1; i <= MAXN; i++) {
    sub[i][0] = 1;
    sub[i + MAXN][1] = 1;
  }
  dfs(1, 1, q);
  for (int i = 1; i <= q; i++) cout << res[i] << " ";
  return 0;
}