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;
namespace io {
char ibuf[(1 << 20)], *iS, *iT, obuf[(1 << 20)],
    *oS = obuf, *oT = oS + (1 << 20) - 1, c, qu[55];
int f, qr;
inline void flush(void) {
  return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void();
}
inline char getch(void) {
  return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20), stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
}
inline void putch(char x) {
  *oS++ = x;
  if (oS == oT) flush();
  return;
}
string getstr(void) {
  string s = "";
  char c = getch();
  while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)
    c = getch();
  while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF))
    s.push_back(c), c = getch();
  return s;
}
void putstr(string str, int begin = 0, int end = -1) {
  if (end == -1) end = str.size();
  for (register int i = begin; i < end; i++) putch(str[i]);
  return;
}
template <typename T>
inline T read() {
  register T x = 0;
  for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
    if (c == '-') f = -1;
  for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
  return x * f;
}
template <typename T>
inline void write(const T& t) {
  register T x = t;
  if (!x) putch('0');
  if (x < 0) putch('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) putch(qu[qr--]);
  return;
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;
vector<pair<int, int> > tree[300005 << 2];
void insert(int p, int l, int r, int ql, int qr, pair<int, int> val) {
  if (ql <= l && r <= qr) return tree[p].push_back(val);
  int mid = (l + r) >> 1;
  if (ql <= mid) insert(p << 1, l, mid, ql, qr, val);
  if (qr > mid) insert(p << 1 | 1, mid + 1, r, ql, qr, val);
  return;
}
map<long long, int> record;
long long answer[300005], siz[2][300005 << 1], sum = 0;
int fa[300005 << 1];
stack<pair<int, int> > S;
int getfa(int p) { return fa[p] == p ? p : getfa(fa[p]); }
void merge(int x, int y) {
  x = getfa(x), y = getfa(y);
  if (siz[0][x] + siz[1][x] < siz[0][y] + siz[1][y]) swap(x, y);
  S.push((pair<int, int>){x, y});
  if (x == y) return;
  fa[y] = x;
  sum -= siz[0][x] * siz[1][x] + siz[0][y] * siz[1][y];
  siz[0][x] += siz[0][y], siz[1][x] += siz[1][y];
  sum += siz[0][x] * siz[1][x];
  return;
}
void rollBack(void) {
  int x = S.top().first, y = S.top().second;
  S.pop();
  if (x == y) return;
  sum -= siz[0][x] * siz[1][x];
  siz[0][x] -= siz[0][y], siz[1][x] -= siz[1][y];
  sum += siz[0][x] * siz[1][x] + siz[0][y] * siz[1][y];
  fa[y] = y;
  return;
}
void dfs(int p, int l, int r) {
  for (vector<pair<int, int> >::iterator i = tree[p].begin();
       i != tree[p].end(); i++)
    merge(i->first, i->second + 300005);
  if (l == r) {
    answer[l] = sum;
    for (vector<pair<int, int> >::iterator i = tree[p].begin();
         i != tree[p].end(); i++)
      rollBack();
    return;
  }
  int mid = (l + r) >> 1;
  dfs(p << 1, l, mid), dfs(p << 1 | 1, mid + 1, r);
  for (vector<pair<int, int> >::iterator i = tree[p].begin();
       i != tree[p].end(); i++)
    rollBack();
  return;
}
int main() {
  int n = read<int>();
  for (register int i = 1; i <= n; i++) {
    pair<int, int> t;
    t.first = read<int>(), t.second = read<int>();
    long long val = 1LL * t.first * 300005 + t.second;
    map<long long, int>::iterator j = record.find(val);
    if (j == record.end())
      record[val] = i;
    else
      insert(1, 1, n, j->second, i - 1, t), record.erase(j);
  }
  for (map<long long, int>::iterator i = record.begin(); i != record.end(); i++)
    insert(1, 1, n, i->second, n,
           (pair<int, int>){i->first / 300005, i->first % 300005});
  record.clear();
  for (register int i = 1; i < 300005; i++)
    fa[i] = i, siz[0][i] = 1, fa[i + 300005] = i + 300005,
    siz[1][i + 300005] = 1;
  dfs(1, 1, n);
  for (register int i = 1; i <= n; i++) write(answer[i]), putch(" \n"[i == n]);
  return 0;
}
