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;
int n;
map<pair<int, int>, int> ft;
vector<pair<int, int>> node_list[3000001];
stack<pair<int, int>> st;
long long sx[3000100], sy[3000010], ans;
int fa[3000010];
int f(int t) {
  if (fa[t] != t) return f(fa[t]);
  return fa[t];
}
void up(int t, int l, int r, int ql, int qr, const pair<int, int> &pt) {
  if (ql <= l && r <= qr) {
    node_list[t].push_back(pt);
    return;
  }
  int mid = (l + r) >> 1;
  if (qr > mid) {
    up(t << 1 | 1, mid + 1, r, ql, qr, pt);
  }
  if (ql <= mid) {
    up(t << 1, l, mid, ql, qr, pt);
  }
}
void solve(int t, int l, int r) {
  int top = st.size();
  long long tmp_ans = ans;
  for (int i = 0; i < node_list[t].size(); ++i) {
    int x = node_list[t][i].first, y = node_list[t][i].second + n;
    if (f(x) == f(y)) continue;
    x = f(x);
    y = f(y);
    if (sx[x] + sy[x] > sx[y] + sy[y]) swap(x, y);
    ans -= sx[x] * sy[x] + sx[y] * sy[y];
    fa[x] = y;
    sx[y] += sx[x];
    sy[y] += sy[x];
    ans += sx[y] * sy[y];
    st.push(make_pair(x, y));
  }
  if (l != r) {
    int mid = (l + r) >> 1;
    solve(t << 1, l, mid);
    solve(t << 1 | 1, mid + 1, r);
  } else {
    printf("%lld ", ans);
  }
  ans = tmp_ans;
  while (st.size() > top) {
    int x = st.top().first;
    int y = st.top().second;
    st.pop();
    fa[x] = x;
    sx[y] -= sx[x];
    sy[y] -= sy[x];
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (ft.find(make_pair(x, y)) == ft.end()) {
      ft[make_pair(x, y)] = i;
    } else {
      up(1, 1, n, ft[make_pair(x, y)], i - 1, make_pair(x, y));
      ft.erase(ft.find(make_pair(x, y)));
    }
  }
  for (auto x : ft) {
    up(1, 1, n, x.second, n, x.first);
  }
  for (int i = 1; i <= n; ++i) {
    fa[i] = i;
    sx[i] = 1;
    sy[i] = 0;
  }
  for (int i = n + 1; i <= n * 2; ++i) {
    fa[i] = i;
    sx[i] = 0;
    sy[i] = 1;
  }
  ans = 0;
  solve(1, 1, n);
  printf("\n");
}
