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 N = (int)6e5;
struct edge {
  int a, b, l, r;
};
int cnt[N + 1], u[N], color[N], deg[N];
int ux[N], uy[N];
long long ans[N];
vector<int> g[N];
void add(int a, int b) { g[a].push_back(b), g[b].push_back(a); }
void dfs(int v, int value, vector<pair<int, int> > &xy) {
  ux[value] += xy[v].first, uy[value] += xy[v].second;
  u[v] = 1, color[v] = value;
  for (int i = 0; i < (int)((int)(g[v]).size()); i++)
    if (!u[g[v][i]]) dfs(g[v][i], value, xy);
}
void go(int l, int r, const vector<edge> &v, int vn, long long add_vn,
        vector<pair<int, int> > &xy, long long xy_sum) {
  if (cnt[l] == cnt[r]) return;
  if (!(int)(v).size()) {
    while (l < r) ans[l++] = xy_sum + add_vn;
    return;
  }
  vector<edge> v1;
  for (int i = 0; i < (int)(vn); i++) g[i].clear();
  for (int i = 0; i < (int)((int)(v).size()); i++)
    if (v[i].a != v[i].b) {
      if (v[i].l <= l && r <= v[i].r)
        add(v[i].a, v[i].b);
      else if (l < v[i].r && v[i].l < r)
        v1.push_back(v[i]);
    }
  int vn1 = 0;
  for (int i = 0; i < (int)(vn); i++) u[i] = 0, ux[i] = uy[i] = 0;
  for (int i = 0; i < (int)(vn); i++)
    if (!u[i]) deg[vn1] = 0, dfs(i, vn1++, xy);
  for (int i = 0; i < (int)((int)(v1).size()); i++) {
    v1[i].a = color[v1[i].a];
    v1[i].b = color[v1[i].b];
    if (v1[i].a != v1[i].b) deg[v1[i].a]++, deg[v1[i].b]++;
  }
  vector<pair<int, int> > xy1;
  xy_sum = 0;
  vn = vn1, vn1 = 0;
  for (int i = 0; i < (int)(vn); i++) {
    u[i] = vn1;
    if (deg[i]) {
      vn1++;
      xy1.push_back(make_pair(ux[i], uy[i]));
      xy_sum += ux[i] * 1LL * uy[i];
    } else {
      add_vn += ux[i] * 1LL * uy[i];
    }
  }
  for (int i = 0; i < (int)((int)(v1).size()); i++) {
    v1[i].a = u[v1[i].a];
    v1[i].b = u[v1[i].b];
  }
  int m = (l + r) / 2;
  go(l, m, v1, vn1, add_vn, xy1, xy_sum);
  go(m, r, v1, vn1, add_vn, xy1, xy_sum);
}
int main() {
  map<pair<int, int>, int> m;
  vector<edge> v;
  int n, k;
  n = N;
  cin >> k;
  k <<= 1;
  for (int i = 0; i < (int)(k); i++) {
    char type = '+';
    if (i & 1) type = 0;
    if (type == '+' || type == '-') {
      int a, b;
      cin >> a >> b;
      a--, b--;
      b += (n >> 1);
      if (m.find(make_pair(a, b)) != m.end() and m[make_pair(a, b)] != -1) {
        type = '-';
      }
      if (type == '+')
        m[make_pair(a, b)] = i;
      else {
        int &j = m[make_pair(a, b)];
        v.push_back({a, b, j, i});
        j = -1;
      }
    } else
      cnt[i + 1]++;
    cnt[i + 1] += cnt[i];
  }
  for (__typeof((m).begin()) it = (m).begin(); it != (m).end(); it++)
    if (it->second != -1)
      v.push_back({it->first.first, it->first.second, it->second, k});
  vector<pair<int, int> > xy;
  for (int i = 0; i < (n >> 1); i++) {
    xy.push_back(make_pair(1, 0));
  }
  for (int i = 0; i < (n >> 1); i++) {
    xy.push_back(make_pair(0, 1));
  }
  go(0, k, v, n, 0, xy, 0);
  for (int i = 0; i < (int)(k); i++)
    if (cnt[i + 1] != cnt[i]) cout << ans[i] << " ";
  cout << "\n";
  return 0;
}