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;
namespace dsu {
int prv[2 * 300000 + 7];
int rnk[2 * 300000 + 7];
pair<int, int> cnt[2 * 300000 + 7];
long long ans;
struct change {
  long long sm;
  int v1, v2;
  int prv1, prv2;
  int rnk1, rnk2;
  pair<int, int> cnt1, cnt2;
  change() {
    sm = 0;
    v1 = v2 = prv1 = prv2 = rnk1 = rnk2 = 0;
    cnt1 = cnt2 = {0, 0};
  }
  change(int _v1, int _v2, long long _ans) {
    sm = _ans;
    v1 = _v1;
    v2 = _v2;
    prv1 = prv[v1];
    prv2 = prv[v2];
    rnk1 = rnk[v1];
    rnk2 = rnk[v2];
    cnt1 = cnt[v1];
    cnt2 = cnt[v2];
  }
};
stack<change> hh;
void init() {
  ans = 0;
  for (int i = 1; i <= 300000; ++i) {
    prv[i] = prv[i + 300000] = -1;
    rnk[i] = rnk[i + 300000] = 0;
    cnt[i] = {1, 0};
    cnt[i + 300000] = {0, 1};
  }
}
int find(int x) {
  if (prv[x] == -1) {
    return x;
  }
  return find(prv[x]);
}
bool unite(int x, int y) {
  int k1 = find(x);
  int k2 = find(y);
  if (k1 == k2) {
    return false;
  }
  hh.push(change(k1, k2, ans));
  ans -= 1LL * cnt[k1].first * cnt[k1].second;
  ans -= 1LL * cnt[k2].first * cnt[k2].second;
  if (rnk[k1] >= rnk[k2]) {
    rnk[k1] += (rnk[k1] == rnk[k2]);
    prv[k2] = k1;
    cnt[k1].first += cnt[k2].first;
    cnt[k1].second += cnt[k2].second;
    ans += 1LL * cnt[k1].first * cnt[k1].second;
  } else {
    prv[k1] = k2;
    cnt[k2].first += cnt[k1].first;
    cnt[k2].second += cnt[k1].second;
    ans += 1LL * cnt[k2].first * cnt[k2].second;
  }
  return true;
}
void undo() {
  if (hh.empty() == true) {
    return;
  }
  change aux = hh.top();
  hh.pop();
  ans = aux.sm;
  prv[aux.v1] = aux.prv1;
  prv[aux.v2] = aux.prv2;
  rnk[aux.v1] = aux.rnk1;
  rnk[aux.v2] = aux.rnk2;
  cnt[aux.v1] = aux.cnt1;
  cnt[aux.v2] = aux.cnt2;
}
};  // namespace dsu
int q;
long long ret[300000 + 1];
vector<pair<int, int> > v[8 * 300000 + 1];
map<pair<int, int>, int> zx;
void update(int where, int IL, int IR, int CURL, int CURR, int x, int y) {
  if (IR < CURL || CURR < IL) {
    return;
  }
  if (CURL <= IL && IR <= CURR) {
    v[where].push_back({x, y});
    return;
  }
  int mid = (IL + IR) / 2;
  update(2 * where, IL, mid, CURL, CURR, x, y);
  update(2 * where + 1, mid + 1, IR, CURL, CURR, x, y);
}
void calc(int where, int IL, int IR) {
  int cnt = 0;
  int sz = v[where].size();
  for (int i = 0; i < sz; ++i) {
    cnt += dsu ::unite(v[where][i].first, v[where][i].second);
  }
  if (IL == IR) {
    ret[IL] = dsu ::ans;
  } else {
    int mid = (IL + IR) / 2;
    calc(2 * where, IL, mid);
    calc(2 * where + 1, mid + 1, IR);
  }
  for (int i = 0; i < cnt; ++i) {
    dsu ::undo();
  }
}
void input() { scanf("%d", &q); }
void solve() {
  for (int i = 1; i <= q; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (zx.find({x, y}) == zx.end()) {
      zx[{x, y}] = i;
    } else {
      int st = zx[{x, y}];
      update(1, 1, q, st, i - 1, x, y + 300000);
      zx.erase({x, y});
    }
  }
  for (auto it = zx.begin(); it != zx.end(); ++it) {
    update(1, 1, q, it->second, q, it->first.first, it->first.second + 300000);
  }
  dsu ::init();
  calc(1, 1, q);
  for (int i = 1; i <= q; ++i) {
    printf("%I64d\n", ret[i]);
  }
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve();
  return 0;
}