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 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, zero = 3e5 + 10;
int P[N * 2], sy[N * 2], sx[N * 2];
long long ans;
int par(int x) {
  if (P[x] == x) return x;
  return par(P[x]);
}
int val[10000000], timer;
int* where[10000000];
void mem(int& x, int y) {
  ++timer;
  val[timer] = x;
  where[timer] = &x;
  x = y;
}
void rollback() {
  (*where[timer]) = val[timer];
  --timer;
}
void join(int x, int y) {
  x = par(x);
  y = par(y);
  if (x == y) return;
  if (sx[x] + sy[x] < sx[y] + sy[y]) swap(x, y);
  ans -= (long long)sx[x] * sy[x] + (long long)sx[y] * sy[y];
  mem(sx[x], sx[x] + sx[y]);
  mem(sy[x], sy[x] + sy[y]);
  mem(P[y], x);
  ans += (long long)sx[x] * sy[x];
}
vector<pair<int, int> > T[4 * N];
void add(int v, int tl, int tr, int l, int r, pair<int, int> p) {
  if (l > tr || r < tl) return;
  if (l <= tl && tr <= r) {
    T[v].push_back({p.first, p.second + zero});
    return;
  }
  int tm = (tl + tr) / 2;
  add(v * 2, tl, tm, l, r, p);
  add(v * 2 + 1, tm + 1, tr, l, r, p);
}
long long A[N];
void dfs(int v, int tl, int tr) {
  long long old_ans = ans;
  int old_timer = timer;
  for (auto i : T[v]) {
    join(i.first, i.second);
  }
  if (tl == tr) {
    A[tl] = ans;
  } else {
    int tm = (tl + tr) / 2;
    dfs(v * 2, tl, tm);
    dfs(v * 2 + 1, tm + 1, tr);
  }
  while (timer != old_timer) {
    rollback();
  }
  ans = old_ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i <= N; i++)
    P[i] = i, P[i + zero] = i + zero, sx[i] = sy[i + zero] = 1;
  int q;
  cin >> q;
  map<pair<int, int>, int> mp;
  for (int i = 1, x, y; i <= q; i++) {
    cin >> x >> y;
    pair<int, int> p = {x, y};
    if (mp.count(p)) {
      add(1, 1, q, mp[p], i - 1, p);
      mp.erase(p);
    } else {
      mp[p] = i;
    }
  }
  for (auto i : mp) add(1, 1, q, i.second, q, i.first);
  dfs(1, 1, q);
  for (int i = 1; i <= q; i++) cout << A[i] << ' ';
}
