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>
const int N = 300005;
std::vector<std::pair<int, int> > vec[N << 2];
std::map<std::pair<int, int>, int> map;
std::stack<std::pair<int, int> > stack;
long long sx[N * 2 + 5], sy[N * 2 + 5], ans;
int fa[N * 2 + 5];
int read() {
  int x = 0, v = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; v = (ch == '-') ? (-1) : (v), ch = getchar())
    ;
  for (; ch <= '9' && ch >= '0'; x = x * 10 + ch - '0', ch = getchar())
    ;
  return x * v;
}
int find(int x) { return (!fa[x]) ? x : find(fa[x]); }
void modify(int now, int tl, int tr, int l, int r, std::pair<int, int> v) {
  if (tl >= l && tr <= r) return (void)(vec[now].push_back(v));
  int mid = (tl + tr) >> 1;
  if (l <= mid) modify(now << 1, tl, mid, l, r, v);
  if (mid + 1 <= r) modify(now << 1 | 1, mid + 1, tr, l, r, v);
}
void solve(int now, int tl, int tr) {
  long long rec = ans;
  int wjp = stack.size();
  for (int i = 0; i < vec[now].size(); ++i) {
    int x = vec[now][i].first, y = vec[now][i].second + N;
    x = find(x), y = find(y);
    if (x == y) continue;
    if (sx[x] + sy[x] > sx[y] + sy[y]) std::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];
    stack.push(std::pair<int, int>(x, y));
  }
  if (tl != tr) {
    int mid = (tl + tr) >> 1;
    solve(now << 1, tl, mid);
    solve(now << 1 | 1, mid + 1, tr);
  } else
    printf("%lld\n", ans);
  ans = rec;
  for (; stack.size() > wjp;) {
    std::pair<int, int> tmp = stack.top();
    stack.pop();
    int x = tmp.first, y = tmp.second;
    fa[x] = 0;
    sx[y] -= sx[x], sy[y] -= sy[x];
  }
}
int main(void) {
  int n = read();
  for (register int i = 1; i <= n; ++i) {
    int x = read(), y = read();
    std::pair<int, int> now = std::pair<int, int>(x, y);
    if (map[now]) {
      modify(1, 1, n, map[now], i - 1, now);
      map.erase(map.find(now));
    } else
      map[now] = i;
  }
  for (auto item : map) {
    modify(1, 1, n, item.second, n, item.first);
  }
  for (register int i = 1; i <= N; ++i) fa[i] = 0, sx[i] = 1;
  for (register int i = 1; i <= N; ++i) fa[i + N] = 0, sy[i + N] = 1;
  solve(1, 1, n);
  return 0;
}
