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;
const double PI = 2 * acos(0.0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";
template <class T0, class T1>
inline ostream &operator<<(ostream &out, pair<T0, T1> &a) {
  return out << "{" << a.first << ", " << a.second << "}";
}
template <class T0, class T1, class T2>
inline ostream &operator<<(ostream &out, tuple<T0, T1, T2> &a) {
  return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a)
             << "}";
}
template <class T0, class T1, class T2, class T3>
inline ostream &operator<<(ostream &out, tuple<T0, T1, T2, T3> &a) {
  return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a)
             << ", " << get<3>(a) << "}";
}
template <class T>
inline ostream &operator<<(ostream &out, vector<T> &a) {
  out << "[";
  for (int i = 0; i < int(a.size()); ++i)
    out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
  return out;
}
void smain();
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(12) << fixed;
  smain();
}
const int N = 2e6 + 100;
const int MID = 3e5 + 10;
const int MEM = 5e6 + 100;
int save[MEM];
int state = 0;
int sz[N][2];
int parent[N];
long long ans = 0;
void set_val(int *ptr, int val) {
  assert(state + 2 < MEM);
  save[state++] = (long long)ptr;
  save[state++] = *ptr;
  *ptr = val;
}
void unset_val() {
  int *ptr = (int *)save[state - 2];
  *ptr = save[state - 1];
  state -= 2;
}
void restore(int old_state) {
  while (state > old_state) {
    unset_val();
  }
}
void make_set(int v) {
  parent[v] = v;
  sz[v][0] = v < MID;
  sz[v][1] = v >= MID;
}
int find_set(int v) { return v == parent[v] ? v : find_set(parent[v]); }
void union_sets(int u, int v) {
  u = find_set(u);
  v = find_set(v);
  if (u == v) return;
  if (sz[u][0] + sz[u][1] < sz[v][0] + sz[v][1]) swap(u, v);
  ans -= 1LL * sz[v][0] * sz[v][1];
  ans -= 1LL * sz[u][0] * sz[u][1];
  set_val(&sz[u][0], sz[u][0] + sz[v][0]);
  set_val(&sz[u][1], sz[u][1] + sz[v][1]);
  set_val(&parent[v], u);
  ans += 1LL * sz[u][0] * sz[u][1];
}
int type[N];
int first[N], second[N];
int neib[N];
void solve(int l, int r) {
  if (l == r) {
    if (type[l] == 2) cout << ans << ' ';
    return;
  }
  int old_state = state;
  long long old_ans = ans;
  int mid = l + r >> 1;
  for (int i = mid + 1; i <= r; ++i) {
    if (type[i] == 0 && neib[i] < l) union_sets(first[i], second[i]);
  }
  solve(l, mid);
  restore(old_state);
  ans = old_ans;
  for (int i = l; i <= mid; ++i) {
    if (type[i] == 1 && neib[i] > r) {
      union_sets(first[i], second[i]);
    }
  }
  solve(mid + 1, r);
  restore(old_state);
  ans = old_ans;
}
map<pair<int, int>, int> points;
void smain() {
  fill(parent, parent + N, -1);
  int q;
  cin >> q;
  vector<tuple<int, int, int> > queries;
  int cnt = 0;
  for (int i = 0; i < int(q); ++i) {
    pair<int, int> point;
    cin >> point.first >> point.second;
    if (points.count(point)) {
      queries.push_back(make_tuple(0, point.first, point.second + MID));
      points.erase(point);
    } else {
      points[point] = cnt++;
      queries.push_back(make_tuple(1, point.first, point.second + MID));
    }
    queries.push_back(make_tuple(2, -1, -1));
  }
  map<pair<int, int>, int> ind;
  int n = queries.size();
  for (int i = 0; i < int(n); ++i) {
    int t, u, v;
    tie(t, u, v) = queries[i];
    type[i] = t;
    first[i] = u;
    second[i] = v;
    pair<int, int> key = {u, v};
    if (t == 1) {
      make_set(u);
      make_set(v);
      ind[key] = i;
      neib[i] = N;
    } else if (t == 0) {
      neib[i] = ind[key];
      ind.erase(key);
      neib[neib[i]] = i;
    }
  }
  solve(0, n - 1);
}
