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;
const int N = 6e5 + 3;
int n;
map<pair<int, int>, int> mp;
map<pair<int, int>, int>::iterator it;
struct hh {
  int fa[N], s1[N], s2[N];
  int find(int x) { return x ^ fa[x] ? find(fa[x]) : x; }
  void set(int n) {
    for (int i = 1; i <= 2 * n; ++i) fa[i] = i;
    for (int i = 1; i <= n; ++i) s1[i] = 1, s2[i + n] = 1;
  }
} f;
struct kk {
  int x, y;
};
struct segment {
  vector<kk> a[N << 2];
  void mdy(int k, int l, int r, int ll, int rr, kk u) {
    if (l >= ll && r <= rr) {
      a[k].push_back(u);
      return;
    }
    int mid = l + r >> 1;
    if (ll <= mid) mdy(k << 1, l, mid, ll, rr, u);
    if (rr > mid) mdy(k << 1 | 1, mid + 1, r, ll, rr, u);
  }
  void solve(int k, int l, int r, long long ans) {
    vector<kk> s;
    for (int i = 0; i < a[k].size(); ++i) {
      int x = f.find(a[k][i].x), y = f.find(a[k][i].y);
      if (x ^ y) {
        ans -= 1ll * f.s1[x] * f.s2[x] + 1ll * f.s1[y] * f.s2[y];
        if (f.s1[x] + f.s2[x] > f.s1[y] + f.s2[y]) swap(x, y);
        f.fa[x] = y, f.s1[y] += f.s1[x], f.s2[y] += f.s2[x];
        ans += 1ll * f.s1[y] * f.s2[y], s.push_back((kk){x, y});
      }
    }
    int mid = l + r >> 1;
    if (l == r)
      printf("%lld ", ans);
    else
      solve(k << 1, l, mid, ans), solve(k << 1 | 1, mid + 1, r, ans);
    for (int i = s.size() - 1; ~i; --i) {
      int x = s[i].x, y = s[i].y;
      ans -= 1ll * f.s1[y] * f.s2[y];
      f.fa[x] = x, f.s1[y] -= f.s1[x], f.s2[y] -= f.s2[x];
      ans += 1ll * f.s1[x] * f.s2[x] + 1ll * f.s1[y] * f.s2[y];
    }
  }
} T;
inline int in() {
  char c;
  int f = 1;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') f = -1;
  int x = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
  return x * f;
}
int main() {
  int x, y;
  n = in();
  for (int i = 1; i <= n; ++i) {
    x = in(), y = in() + 3e5;
    if (!mp[make_pair(x, y)])
      mp[make_pair(x, y)] = i;
    else
      T.mdy(1, 1, n, mp[make_pair(x, y)], i - 1, (kk){x, y}),
          mp[make_pair(x, y)] = 0;
  }
  for (it = mp.begin(); it != mp.end(); ++it)
    if (it->second)
      T.mdy(1, 1, n, it->second, n, (kk){it->first.first, it->first.second});
  f.set(3e5);
  T.solve(1, 1, n, 0);
  return 0;
}