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;
template <class T>
inline void amin(T &x, const T &y) {
  if (y < x) x = y;
}
template <class T>
inline void amax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class Iter>
void rprintf(const char *fmt, Iter begin, Iter end) {
  for (bool sp = 0; begin != end; ++begin) {
    if (sp)
      putchar(' ');
    else
      sp = true;
    printf(fmt, *begin);
  }
  putchar('\n');
}
int Q;
struct Point {
  int x, y, i;
  bool operator<(const Point &o) const {
    return x != o.x ? x < o.x : y != o.y ? y < o.y : i < o.i;
  }
} P[300011];
struct Node {
  int parent;
  int x_cnt, y_cnt;
  int time;
  Node(int parent_, int x_cnt_, int y_cnt_, int time_) {
    parent = parent_;
    x_cnt = x_cnt_;
    y_cnt = y_cnt_;
    time = time_;
  }
  int size() const { return x_cnt + y_cnt; }
  long long eval() const { return (long long)x_cnt * y_cnt; }
};
const int LIMIT = 300011;
vector<Node> nodes[LIMIT * 2];
vector<int> update;
int stamp = 0;
int Uroot(int x) {
  while (nodes[x].back().parent != x) {
    x = nodes[x].back().parent;
  }
  return x;
}
long long Ulink(int x, int y) {
  x = Uroot(x);
  y = Uroot(y);
  if (x == y) return 0;
  if (nodes[x].back().size() > nodes[y].back().size()) swap(x, y);
  long long ret = -nodes[x].back().eval() - nodes[y].back().eval();
  nodes[y].emplace_back(y, nodes[y].back().x_cnt + nodes[x].back().x_cnt,
                        nodes[y].back().y_cnt + nodes[x].back().y_cnt, stamp);
  nodes[x].emplace_back(y, 0, 0, stamp);
  update.push_back(x);
  update.push_back(y);
  ret += nodes[y].back().eval();
  return ret;
}
long long Uins(int x, int y) {
  y += LIMIT;
  if (nodes[x].empty()) {
    nodes[x].emplace_back(x, 1, 0, stamp);
    update.push_back(x);
  }
  if (nodes[y].empty()) {
    nodes[y].emplace_back(y, 0, 1, stamp);
    update.push_back(y);
  }
  return Ulink(x, y);
}
const int SIZE = 1 << 19;
vector<pair<int, int> > seg[SIZE * 2];
void add(int x, int y, const pair<int, int> &p, int k, int l, int r) {
  if (y <= l || r <= x) {
  } else if (x <= l && r <= y) {
    seg[k].push_back(p);
  } else {
    add(x, y, p, k * 2, l, (l + r) / 2);
    add(x, y, p, k * 2 + 1, (l + r) / 2, r);
  }
}
void add(int x, int y, const pair<int, int> &p) { add(x, y, p, 1, 0, SIZE); }
long long answer;
long long ans[SIZE];
void run(int k, int l, int r) {
  const long long answer_bak = answer;
  stamp++;
  for (__typeof((seg[k]).begin()) e = (seg[k]).begin(), e_end = (seg[k]).end();
       e != e_end; ++e) {
    answer += Uins(e->first, e->second);
  }
  if (l + 1 == r) {
    ans[k - SIZE] = answer;
  } else {
    run(k * 2, l, (l + r) / 2);
    run(k * 2 + 1, (l + r) / 2, r);
  }
  while (!update.empty()) {
    int x = update.back();
    if (nodes[x].back().time == stamp) {
      nodes[x].pop_back();
      update.pop_back();
    } else {
      break;
    }
  }
  answer = answer_bak;
  stamp--;
}
void run() { run(1, 0, SIZE); }
void MAIN() {
  scanf("%d", &Q);
  for (int i = 0, i_len = (Q); i < i_len; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    P[i].x = x;
    P[i].y = y;
    P[i].i = i;
  }
  sort(P, P + Q);
  for (int i = 0; i < Q;) {
    int j = i;
    while (j < Q && P[i].x == P[j].x && P[i].y == P[j].y) j++;
    for (int k = i; k < j; k += 2) {
      int right;
      if (k + 1 < j)
        right = P[k + 1].i;
      else
        right = SIZE;
      add(P[k].i, right, make_pair(P[k].x, P[k].y));
    }
    i = j;
  }
  run();
  rprintf("%lld", ans, ans + Q);
}
int main() {
  int TC = 1;
  for (int tc = 0, tc_len = (TC); tc < tc_len; ++tc) MAIN();
  return 0;
}