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>
#pragma GCC optimize(                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           \
    "-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2", \
    3)
#pragma GCC target("avx", "sse2")
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
long long read() {
  char ch = getchar();
  long long x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int N = 6e5 + 10;
const int diff = 3e5;
int Q;
struct node {
  int pos, to, h;
  long long cntx, cnty;
  node(int pos, int to, int h, long long cntx, long long cnty) {
    this->pos = pos, this->to = to, this->h = h, this->cntx = cntx,
    this->cnty = cnty;
  }
};
struct DSU {
  int par[N], height[N];
  long long cntx[N], cnty[N];
  long long sum = 0;
  DSU() {
    for (int i = 1; i <= 6e5 + 1; i++) {
      par[i] = i, height[i] = 1;
      if (i <= 3e5)
        cntx[i] = 1;
      else
        cnty[i] = 1;
    }
  }
  int find(int x) { return x == par[x] ? x : find(par[x]); }
  int unit(int x, int y, stack<node> &st) {
    x = find(x), y = find(y);
    if (x == y) return 0;
    if (height[x] < height[y]) swap(x, y);
    node sttemp(y, x, height[y], cntx[y], cnty[y]);
    st.push(sttemp);
    sum -= cntx[x] * cnty[x];
    sum -= cntx[y] * cnty[y];
    cntx[x] += cntx[y];
    cnty[x] += cnty[y];
    sum += cntx[x] * cnty[x];
    par[y] = x;
    height[x] += height[y];
    return 1;
  }
  void del(stack<node> &st) {
    while (st.size()) {
      node temp = st.top();
      st.pop();
      par[temp.pos] = temp.pos;
      height[temp.to] -= temp.h;
      sum -= cntx[temp.to] * cnty[temp.to];
      cntx[temp.to] -= temp.cntx;
      cnty[temp.to] -= temp.cnty;
      sum += cntx[temp.to] * cnty[temp.to];
      sum += temp.cntx * temp.cnty;
    }
  }
} dsu;
struct SEG {
  vector<pair<int, int> > tr[N << 2];
  void update(int l, int r, int root, int lf, int rt, pair<int, int> val) {
    if (lf <= l && r <= rt) {
      tr[root].push_back(val);
      return;
    }
    int mid = (l + r) >> 1;
    if (lf <= mid) update(l, mid, root << 1, lf, rt, val);
    if (rt > mid) update(mid + 1, r, root << 1 | 1, lf, rt, val);
  }
  void query(int l, int r, int root) {
    stack<node> st;
    for (auto k : tr[root]) {
      dsu.unit(k.first, k.second + diff, st);
    }
    if (l == r) {
      printf("%lld ", dsu.sum);
      dsu.del(st);
      return;
    }
    int mid = (l + r) >> 1;
    query(l, mid, root << 1);
    query(mid + 1, r, root << 1 | 1);
    dsu.del(st);
  }
} sgt;
map<pair<int, int>, pair<int, int> > mp;
struct nd {
  int x, y, st, ed;
};
vector<nd> query;
int main() {
  Q = read();
  int x, y;
  for (int i = 1; i <= Q; i++) {
    x = read(), y = read();
    if (mp[{x, y}].first) {
      query.push_back(nd{x, y, mp[{x, y}].first, i - 1});
      mp[{x, y}].first = 0;
    } else {
      mp[{x, y}].first = i;
    }
  }
  for (auto k : mp) {
    if (k.second.first)
      query.push_back(nd{k.first.first, k.first.second, k.second.first, Q});
  }
  for (auto k : query) {
    sgt.update(1, Q, 1, k.st, k.ed, make_pair(k.x, k.y));
  }
  sgt.query(1, Q, 1);
  return 0;
}