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 long long MOD = 1e9 + 7;
class DynamicConnectivity {
  void __dfs(int v, int l, int r, vector<long long>& res) {
    long long last_ans = ans;
    int state = cur;
    for (auto x : T[v]) merge(x.first, x.second + K);
    if (l == r - 1)
      res[l] = ans;
    else {
      int m = (l + r) / 2;
      __dfs(v * 2 + 1, l, m, res);
      __dfs(v * 2 + 2, m, r, res);
    }
    while (cur != state) rollback();
    ans = last_ans;
  };

 public:
  static const int N = 300043;
  static const int K = 300000;
  vector<int> p, s1, s2;
  long long ans = 0;
  vector<int*> where;
  vector<int> val;
  int cur = 0;
  vector<vector<pair<int, int>>> T;
  DynamicConnectivity() {
    p = vector<int>(2 * N);
    s1 = vector<int>(2 * N);
    s2 = vector<int>(2 * N);
    where = vector<int*>(4 * N);
    val = vector<int>(4 * N);
    T = vector<vector<pair<int, int>>>(4 * N);
    for (int i = 0; i < K; i++) {
      p[i] = i;
      p[i + K] = i + K;
      s1[i] = 1;
      s2[i + K] = 1;
    }
  }
  void change(int& x, int y) {
    where[cur] = &x;
    val[cur] = x;
    x = y;
    cur++;
  }
  void rollback() {
    cur--;
    (*where[cur]) = val[cur];
  }
  int get(int x) {
    if (p[x] == x) return x;
    return get(p[x]);
  }
  void merge(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) return;
    ans -= s1[x] * 1ll * s2[x];
    ans -= s1[y] * 1ll * s2[y];
    if (s1[x] + s2[x] < s1[y] + s2[y]) swap(x, y);
    change(p[y], x);
    change(s1[x], s1[x] + s1[y]);
    change(s2[x], s2[x] + s2[y]);
    ans += s1[x] * 1ll * s2[x];
  }
  void add(int v, int l, int r, int L, int R, pair<int, int> val) {
    if (L >= R) return;
    if (L == l && R == r)
      T[v].push_back(val);
    else {
      int m = (l + r) / 2;
      add(v * 2 + 1, l, m, L, min(R, m), val);
      add(v * 2 + 2, m, r, max(m, L), R, val);
    }
  }
  vector<long long> dfs(int v, int l, int r) {
    vector<long long> vec(N);
    __dfs(v, l, r, vec);
    return vec;
  }
};
int main() {
  int q;
  cin >> q;
  map<pair<int, int>, int> last;
  DynamicConnectivity dsu;
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    pair<int, int> p = make_pair(x, y);
    if (last.count(p)) {
      dsu.add(0, 0, q, last[p], i, p);
      last.erase(p);
    } else
      last[p] = i;
  }
  for (auto x : last) dsu.add(0, 0, q, x.second, q, x.first);
  vector<long long> res = dsu.dfs(0, 0, q);
  for (int i = 0; i < q; i++) cout << res[i] << " ";
  cout << endl;
}