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 mo = 998244353, G = 3;
inline int read() {
  static int x;
  scanf("%d", &x);
  return x;
}
const int N = 3e5 + 5;
int n, m;
long long res, ans[N];
struct ufs {
  int n, fa[N << 1], sz[N << 1], cx[N << 1], cy[N << 1];
  int top;
  struct info {
    int x, y, s, cx, cy;
  } st[N];
  void init(int n) {
    this->n = n * 2, top = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1, cx[i] = 1;
    for (int i = n + 1; i <= n + n; ++i) fa[i] = i, sz[i] = 1, cy[i] = 1;
  }
  int get(int x) { return fa[x] == x ? x : get(fa[x]); }
  bool test(int x, int y, bool mer) {
    if ((x = get(x)) == (y = get(y))) return 1;
    if (mer) {
      res -= 1ll * cx[x] * cy[x], res -= 1ll * cx[y] * cy[y];
      if (sz[x] > sz[y]) swap(x, y);
      st[++top] = (info){x, y, sz[y], cx[y], cy[y]};
      fa[x] = y, sz[y] += sz[x], cx[y] += cx[x], cy[y] += cy[x];
      res += 1ll * cx[y] * cy[y];
    }
    return 0;
  }
  void undo() {
    int x = st[top].x, y = st[top].y;
    res -= 1ll * cx[y] * cy[y];
    fa[x] = x, sz[y] = st[top].s, cx[y] = st[top].cx, cy[y] = st[top].cy, --top;
    res += 1ll * cx[x] * cy[x], res += 1ll * cx[y] * cy[y];
  }
} U;
map<pair<int, int>, int> app;
set<pair<int, int> > add[N << 2];
pair<int, int> q[N];
void solve(int o, int l, int r) {
  int c = 0;
  for (auto x : add[o])
    if (!U.test(x.first, x.second, 1)) ++c;
  if (l == r)
    ans[l] = res;
  else {
    solve((o << 1), l, ((l + r) >> 1));
    solve((o << 1 | 1), ((l + r) >> 1) + 1, r);
  }
  for (; c; --c) U.undo();
}
void insert(int o, int l, int r, int x, int y, pair<int, int> v) {
  if (x <= l && r <= y) {
    add[o].insert(v);
    return;
  }
  if (x <= ((l + r) >> 1)) insert((o << 1), l, ((l + r) >> 1), x, y, v);
  if (y > ((l + r) >> 1)) insert((o << 1 | 1), ((l + r) >> 1) + 1, r, x, y, v);
}
int main() {
  n = read(), m = 3e5, U.init(m);
  for (int i = 1; i <= n; ++i) {
    q[i].first = read(), q[i].second = read() + m;
    if (app.count(q[i])) {
      insert(1, 1, n, app[q[i]], i - 1, q[i]);
      app.erase(q[i]);
    } else
      app[q[i]] = i;
  }
  for (auto x : app) insert(1, 1, n, x.second, n, x.first);
  solve(1, 1, n);
  for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
  return 0;
}
