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 long long N = 3e5 + 7;
const long long V = N << 1;
long long q;
map<pair<long long, long long>, long long> pr;
pair<long long, long long> e[N];
vector<pair<long long, long long> > tree[N << 2];
void add(long long second, long long tl, long long tr, long long l, long long r,
         pair<long long, long long> e) {
  if (tr < l || r < tl) return;
  if (l <= tl && tr <= r) {
    tree[second].push_back(e);
    return;
  }
  long long tm = (tl + tr) >> 1;
  add(second * 2 + 1, tl, tm, l, r, e);
  add(second * 2 + 2, tm + 1, tr, l, r, e);
}
long long par[V];
long long cnt[V][2];
long long root(long long first) {
  while (par[first] != first) first = par[first];
  return first;
}
vector<pair<long long&, long long> > st;
long long get(long long first) { return cnt[first][0] * cnt[first][1]; }
long long ans = 0;
void merge(long long first, long long second) {
  first = root(first);
  second = root(second);
  if (first == second) return;
  if (cnt[second][0] + cnt[second][1] < cnt[first][0] + cnt[first][1])
    swap(first, second);
  st.push_back({ans, ans});
  ans -= get(first);
  ans -= get(second);
  st.push_back({par[first], par[first]});
  par[first] = second;
  st.push_back({cnt[second][0], cnt[second][0]});
  st.push_back({cnt[second][1], cnt[second][1]});
  cnt[second][0] += cnt[first][0];
  cnt[second][1] += cnt[first][1];
  ans += get(second);
}
void add(pair<long long, long long> e) { merge(e.first, e.second); }
void rollback(long long sz) {
  while (st.size() > sz) {
    st.back().first = st.back().second;
    st.pop_back();
  }
}
void solve(long long second, long long tl, long long tr) {
  long long sz = st.size();
  for (auto e : tree[second]) {
    add(e);
  }
  if (tl == tr) {
    cout << ans << ' ';
  } else {
    long long tm = (tl + tr) >> 1;
    solve(second * 2 + 1, tl, tm);
    solve(second * 2 + 2, tm + 1, tr);
  }
  rollback(sz);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (long long i = 0; i < V; ++i) {
    par[i] = i;
    cnt[i][0] = i < N;
    cnt[i][1] = N <= i;
  }
  cin >> q;
  for (long long i = 0; i < q; ++i) {
    cin >> e[i].first >> e[i].second;
    e[i].second += N;
    if (pr.find(e[i]) != pr.end()) {
      add(0, 0, q - 1, pr[e[i]], i - 1, e[i]);
      pr.erase(e[i]);
    } else {
      pr[e[i]] = i;
    }
  }
  for (auto e : pr) {
    add(0, 0, q - 1, e.second, q - 1, e.first);
  }
  solve(0, 0, q - 1);
  cout << '\n';
}
