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;
using LL = long long;
constexpr int N = 3E5;
vector<pair<int, int>> e[4 * N];
int f[N], fa[N], cnt[N];
vector<pair<int *, int>> stk;
LL ans;
int find(int x) {
  while (fa[x] >= 0) x = fa[x];
  return x;
}
void rangeCover(int p, int l, int r, int s, int t, const pair<int, int> &v) {
  if (l >= t || r <= s) return;
  if (l >= s && r <= t) {
    e[p].push_back(v);
    return;
  }
  int mid = (l + r) / 2;
  rangeCover(2 * p, l, mid, s, t, v);
  rangeCover(2 * p + 1, mid, r, s, t, v);
}
void solve(int p, int l, int r) {
  int clc = (int)stk.size();
  LL bak = ans;
  for (auto v : e[p]) {
    int x, y;
    tie(x, y) = v;
    y = find(y);
    if (f[x] == -1) {
      stk.emplace_back(&f[x], -1);
      f[x] = y;
      stk.emplace_back(&cnt[y], cnt[y]);
      ++cnt[y];
      ans -= fa[y];
    } else {
      int z = find(f[x]);
      if (y == z) continue;
      if (fa[y] < fa[z]) swap(y, z);
      ans += 1LL * fa[y] * cnt[y] + 1LL * fa[z] * cnt[z];
      stk.emplace_back(&fa[z], fa[z]);
      fa[z] += fa[y];
      stk.emplace_back(&fa[y], fa[y]);
      fa[y] = z;
      stk.emplace_back(&cnt[z], cnt[z]);
      cnt[z] += cnt[y];
      ans -= 1LL * fa[z] * cnt[z];
    }
  }
  if (r - l == 1) {
    cout << ans << " ";
  } else {
    int mid = (l + r) / 2;
    solve(2 * p, l, mid);
    solve(2 * p + 1, mid, r);
  }
  while ((int)stk.size() > clc) {
    *stk.back().first = stk.back().second;
    stk.pop_back();
  }
  ans = bak;
}
int main() {
  memset(f, -1, sizeof(f));
  memset(fa, -1, sizeof(fa));
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int q;
  cin >> q;
  map<pair<int, int>, int> in;
  for (int i = 0; i < q; ++i) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    if (in.count({x, y})) {
      rangeCover(1, 0, q, in[{x, y}], i, {x, y});
      in.erase({x, y});
    } else {
      in[{x, y}] = i;
    }
  }
  for (auto p : in) rangeCover(1, 0, q, p.second, q, p.first);
  solve(1, 0, q);
  cout << endl;
  return 0;
}
