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;
const int M = 1000000007;
const int MM = 998244353;
const long double PI = acos(-1);
template <typename T, typename U>
static inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
static inline void amax(T &x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << '(' << p.first << "," << p.second << ')';
}
const int N = 300000;
struct dsu_node {
  int x, rnkx, y, rnky;
  int sz0, sz1;
  long long ans;
  dsu_node() {}
  dsu_node(int x_, int rnkx_, int y_, int rnky_, long long ans_, int xx, int yy)
      : x(x_), y(y_), rnkx(rnkx_), rnky(rnky_), ans(ans_), sz0(xx), sz1(yy) {}
};
struct dsu_with_rollback {
  long long ans = 0;
  vector<int> r, p;
  vector<vector<int>> sz;
  int comps;
  stack<dsu_node> st;
  dsu_with_rollback() {}
  dsu_with_rollback(int n) : comps(n) {
    r.resize(n + 2);
    p.resize(n + 2);
    sz.resize(n + 1);
    for (int i = 0; i <= n; ++i) {
      p[i] = i, r[i] = 0;
      sz[i].resize(2);
      if (i <= N)
        ++sz[i][0];
      else
        ++sz[i][1];
    }
    ans = 0;
  }
  inline int parent(int i) { return (i == p[i]) ? i : parent(p[i]); }
  bool merge(int x, int y) {
    x = parent(x), y = parent(y);
    if (x == y) return false;
    if (r[x] > r[y]) swap(x, y);
    st.push(dsu_node(x, r[x], y, r[y], ans, sz[x][0], sz[x][1]));
    p[x] = y;
    ans -= sz[x][0] * 1ll * sz[x][1];
    ans -= sz[y][0] * 1ll * sz[y][1];
    sz[y][0] += sz[x][0], sz[y][1] += sz[x][1];
    ans += sz[y][0] * 1ll * sz[y][1];
    if (r[x] == r[y]) ++r[y];
    --comps;
    return true;
  }
  void rollback() {
    if (st.empty()) return;
    dsu_node val = st.top();
    st.pop();
    ++comps;
    p[val.x] = val.x, p[val.y] = val.y;
    r[val.x] = val.rnkx, r[val.y] = val.rnky;
    sz[val.y][1] -= val.sz1;
    sz[val.y][0] -= val.sz0;
    ans = val.ans;
  }
};
struct query {
  int x, y;
  query(int x_, long long y_) : x(x_), y(y_) {}
};
struct Tree {
  vector<vector<query>> tree;
  dsu_with_rollback dsu;
  int n, T;
  vector<long long> ans;
  Tree(int n_, int T_) : n(n_), T(T_) {
    dsu = dsu_with_rollback(n);
    tree.resize(4 * T + 10);
    ans.resize(T + 4);
  }
  void rupdate(int v, int st, int en, int l, int r, query &q) {
    if (st > r || en < l) return;
    if (st >= l && en <= r) {
      tree[v].push_back(q);
      return;
    }
    int mid = (st + en) >> 1;
    rupdate(v << 1, st, mid, l, r, q);
    rupdate(v << 1 | 1, mid + 1, en, l, r, q);
  }
  inline void add_edge(int l, int r, int x, int y) {
    query q(x, y);
    rupdate(1, 0, T - 1, l, r, q);
  }
  void dfs(int v, int st, int en) {
    if (en < st) return;
    int cnt = 0;
    for (auto &k : tree[v]) {
      cnt += dsu.merge(k.x, k.y);
    }
    if (st == en)
      ans[st] = dsu.ans;
    else {
      int mid = (st + en) >> 1;
      dfs(v << 1, st, mid);
      dfs(v << 1 | 1, mid + 1, en);
    }
    while (cnt--) dsu.rollback();
  }
  void solve() { dfs(1, 0, T - 1); }
};
int _runtimeTerror_() {
  int Q;
  int n = 300000;
  cin >> Q;
  Tree dsu(2 * n, Q);
  map<pair<int, int>, int> id;
  for (int i = 0; i < Q; ++i) {
    int x, y;
    cin >> x >> y;
    if (id.count({x, y})) {
      dsu.add_edge(id[{x, y}], i - 1, x, y + n);
      id.erase({x, y});
    } else {
      id[{x, y}] = i;
    }
  }
  for (auto &j : id)
    dsu.add_edge(j.second, Q - 1, j.first.first, j.first.second + n);
  dsu.solve();
  for (int i = 0; i < Q; ++i) cout << dsu.ans[i] << " ";
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int TESTS = 1;
  while (TESTS--) _runtimeTerror_();
  return 0;
}
