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;
using ll = long long;
using ld = long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const ld pi = acos(0) * 2;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
template <typename CT, typename T>
inline void reset_container(CT &c, int sz, T v) {
  c.resize(sz);
  for (auto &x : c) x = v;
}
int q;
map<pair<int, int>, int> M;
vector<pair<int, int>> backr;
vector<pair<int, int>> backw;
int r[600001];
int w[600001];
int root(int u) {
  while (r[u] > 0) u = r[u];
  return u;
}
ll ans[300001];
ll now;
void change(int u, ll s) { now += s * (-r[u] - w[u]) * (w[u]); }
void unite(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return;
  if (r[u] > r[v]) swap(u, v);
  backr.push_back(make_pair(v, r[v]));
  backw.push_back(make_pair(u, w[u]));
  backr.push_back(make_pair(u, r[u]));
  change(u, -1);
  change(v, -1);
  r[u] += r[v];
  w[u] += w[v];
  r[v] = u;
  change(u, 1);
}
void roll_back() {
  while (backr.back().first != -1) {
    change(backr.back().first, -1);
    r[backr.back().first] = backr.back().second;
    w[backw.back().first] = backw.back().second;
    change(backr.back().first, 1);
    backr.pop_back();
    backw.pop_back();
    r[backr.back().first] = backr.back().second;
    change(backr.back().first, 1);
    backr.pop_back();
  }
  backr.pop_back();
  backw.pop_back();
}
class segment_tree {
 public:
  using pointer = segment_tree *;
  pointer left, right;
  int l, r, m;
  vector<pair<int, int>> q;
  segment_tree(int l, int r) {
    this->l = l;
    this->r = r;
    m = (l + r) / 2;
    q.clear();
    if (l != r) {
      left = new segment_tree(l, m);
      right = new segment_tree(m + 1, r);
    } else
      left = right = nullptr;
  }
  void update(int u, int v, pair<int, int> p) {
    if (l > v || r < u) return;
    if (u <= l && v >= r) {
      q.push_back(p);
    } else {
      left->update(u, v, p);
      right->update(u, v, p);
    }
  }
  void query() {
    backr.push_back(make_pair(-1, 0));
    backw.push_back(make_pair(-1, 0));
    for (auto p : q) unite(p.first, p.second);
    if (l != r) {
      left->query();
      right->query();
    } else
      ans[l] = now;
    roll_back();
  }
};
segment_tree::pointer tree;
int main() {
  read(q);
  for (int i = (1); i <= (600000); i++) r[i] = -1;
  for (int i = (1); i <= (300000); i++) w[i] = 1;
  tree = new segment_tree(1, q);
  for (int i = (1); i <= (q); i++) {
    pair<int, int> p;
    read(p.first);
    read(p.second);
    p.second += 300000;
    if (M.find(p) != M.end()) {
      tree->update(M[p], i - 1, p);
      M.erase(p);
    } else
      M[p] = i;
  }
  for (auto p : M) tree->update(p.second, q, p.first);
  tree->query();
  for (int i = (1); i <= (q); i++) write(ans[i]), putchar(" \n"[i == q]);
}
