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;
void JIZZ(string output = "") {
  cout << output;
  exit(0);
}
const long double PI = 3.14159265358979323846264338327950288;
const long double eps = 1e-10;
const long long mod = 1e9 + 7;
vector<pair<int, int>> pts[300005 * 4];
void modify(int o, int l, int r, int ml, int mr, int x, int y) {
  if (r < ml || mr < l) return;
  if (ml <= l && r <= mr) {
    pts[o].emplace_back(x, y);
    return;
  }
  modify(((o << 1)), l, ((l + r) >> 1), ml, mr, x, y);
  modify(((o << 1) | 1), ((l + r) >> 1) + 1, r, ml, mr, x, y);
}
long long now;
long long djs[300005 * 2], gx[300005 * 2], gy[300005 * 2], sz[300005 * 2],
    ans[300005];
int Find(int x) { return x == djs[x] ? x : Find(djs[x]); }
void op(stack<pair<long long *, long long>> &hi, pair<int, int> p) {
  int x = p.first, y = p.second;
  const int o = 300000;
  x = Find(x);
  y = Find(o + y);
  if (x == y) return;
  if (sz[x] < sz[y]) swap(x, y);
  hi.emplace(&now, now);
  hi.emplace(&djs[y], djs[y]);
  hi.emplace(&sz[x], sz[x]);
  hi.emplace(&gx[x], gx[x]);
  hi.emplace(&gy[x], gy[x]);
  now -= gx[x] * gy[x];
  now -= gx[y] * gy[y];
  djs[y] = djs[x];
  sz[x] += sz[y];
  gx[x] += gx[y];
  gy[x] += gy[y];
  now += gx[x] * gy[x];
}
void dfs(int o, int l, int r) {
  stack<pair<long long *, long long>> hi;
  for (auto &p : pts[o]) {
    op(hi, p);
  }
  if (l == r) {
    ans[l] = now;
  } else {
    dfs(((o << 1)), l, ((l + r) >> 1));
    dfs(((o << 1) | 1), ((l + r) >> 1) + 1, r);
  }
  while (hi.size()) {
    auto &p = hi.top();
    *p.first = p.second;
    hi.pop();
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  map<pair<int, int>, int> mp;
  for (int i = 1; i <= n; ++i) {
    int x, y;
    cin >> x >> y;
    auto it = mp.find(make_pair(x, y));
    if (it == mp.end()) {
      mp[make_pair(x, y)] = i;
    } else {
      modify(1, 1, n, it->second, i - 1, x, y);
      mp.erase(it);
    }
  }
  for (auto &p : mp) {
    modify(1, 1, n, p.second, n, p.first.first, p.first.second);
  }
  for (int i = 1; i <= 300000; ++i) {
    djs[i] = i;
    gx[i] = 1;
    sz[i] = 1;
  }
  for (int i = 300001; i <= 600000; ++i) {
    djs[i] = i;
    gy[i] = 1;
    sz[i] = 1;
  }
  dfs(1, 1, n);
  for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
  cout << endl;
}
