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>
int repr[2 * 300005], sL[2 * 300005], sR[2 * 300005];
std::stack<std::pair<int, int> > stack;
int Find(int a) {
  while (a != repr[a]) a = repr[a];
  return a;
}
long long Union(int a, int b) {
  a = Find(a);
  b = Find(b);
  if (a == b) {
    stack.push(std::make_pair(-1, -1));
    return 0;
  }
  if (sL[a] + sR[a] > sL[b] + sR[b]) std::swap(a, b);
  long long last = 1ll * sL[a] * sR[a] + 1ll * sL[b] * sR[b];
  stack.push(std::make_pair(a, b));
  sL[b] += sL[a];
  sR[b] += sR[a];
  repr[a] = b;
  return 1ll * sL[b] * sR[b] - last;
}
long long Revert() {
  std::pair<int, int> c = stack.top();
  stack.pop();
  if (c.first == -1) return 0;
  long long last = 1ll * sL[c.second] * sR[c.second];
  sL[c.second] -= sL[c.first];
  sR[c.second] -= sR[c.first];
  repr[c.first] = c.first;
  return 1ll * sL[c.first] * sR[c.first] + 1ll * sL[c.second] * sR[c.second] -
         last;
}
const int LOG = 19;
std::vector<std::pair<int, int> > t[1 << (LOG + 1)];
void add(int a, int b, std::pair<int, int> ed) {
  a += 1 << LOG;
  b += (1 << LOG) + 1;
  while (a < b) {
    if (a & 1) t[a++].push_back(ed);
    if (b & 1) t[--b].push_back(ed);
    a >>= 1;
    b >>= 1;
  }
}
int q;
long long ans = 0;
void dfs(int v = 1, int lo = 0, int hi = (1 << LOG) - 1) {
  for (auto &i : t[v]) ans += Union(i.first, i.second);
  if (lo == hi) {
    if (lo >= q) std::exit(0);
    std::cout << ans << " ";
  } else {
    dfs(v << 1, lo, (lo + hi) / 2);
    dfs((v << 1) + 1, (lo + hi) / 2 + 1, hi);
  }
  for (int i = 0; i < ((int)(t[v]).size()); ++i) ans += Revert();
}
std::map<std::pair<int, int>, int> map;
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  for (int i = 0; i < (3 * 100000); ++i) {
    repr[i] = i;
    sL[i] = 1;
  }
  for (int i = 0; i < (3 * 100000); ++i) {
    repr[3 * 100000 + i] = 3 * 100000 + i;
    sR[3 * 100000 + i] = 1;
  }
  std::cin >> q;
  for (int i = 0; i < (q); ++i) {
    int a, b;
    std::cin >> a >> b;
    a--;
    b--;
    b += 3 * 100000;
    if (map.count(std::make_pair(a, b))) {
      add(map[std::make_pair(a, b)], i - 1, std::make_pair(a, b));
      map.erase(std::make_pair(a, b));
    } else {
      map[std::make_pair(a, b)] = i;
    }
  }
  for (auto &pr : map) {
    add(pr.second, q, pr.first);
  }
  dfs();
  return 0;
}