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>
using namespace std;
class DS {
 public:
  DS(int rows, int cols) : _rows(rows), _cols(cols), _ans(0) {
    int n = rows + cols;
    _p.resize(n, -1);
    _r.resize(n, 0);
    _nr.resize(n, 0);
    _nc.resize(n, 0);
    for (int i = 0; i < rows; ++i) _nr[i] = 1;
    for (int i = 0; i < cols; ++i) _nc[rows + i] = 1;
  }
  long long ans() { return _ans; }
  int find(int i) {
    while (_p[i] >= 0) i = _p[i];
    return i;
  }
  void merge(int r, int c) {
    int i = find(r);
    int j = find(_rows + c);
    if (i == j) return;
    if (_r[i] > _r[j]) swap(i, j);
    _rb.push_back({i, j, _r[j]});
    _p[i] = j;
    if (_r[i] == _r[j]) ++_r[j];
    _ans += (long long)_nr[i] * _nc[j] + (long long)_nc[i] * _nr[j];
    _nr[j] += _nr[i];
    _nc[j] += _nc[i];
  }
  int current_snapshot() { return _rb.size(); }
  void rollback(int snapshot) {
    while (_rb.size() > snapshot) {
      int i = _rb.back().i;
      int j = _rb.back().j;
      int r = _rb.back().r;
      _rb.pop_back();
      _p[i] = -1;
      _r[j] = r;
      _nr[j] -= _nr[i];
      _nc[j] -= _nc[i];
      _ans -= (long long)_nr[i] * _nc[j] + (long long)_nc[i] * _nr[j];
    }
  }

 private:
  int _rows, _cols;
  vector<int> _p, _r, _nr, _nc;
  struct rb_t {
    int i, j, r;
  };
  vector<rb_t> _rb;
  long long _ans;
};
class Solution {
 public:
  Solution(vector<pair<int, int>> const& p, int mx, int my)
      : _n(p.size()), _p(p), _seg(4 * _n), _ds(mx + 1, my + 1) {}
  void solve() {
    map<pair<int, int>, int> t;
    for (int i = 0; i < _n; ++i) {
      auto it = t.find(_p[i]);
      if (it == t.end()) {
        t[_p[i]] = i;
        continue;
      }
      int j = it->second;
      t.erase(it);
      add_pt(0, 0, _n, j, i, _p[i]);
    }
    for (const auto& ti : t) {
      add_pt(0, 0, _n, ti.second, _n, ti.first);
    }
    dfs(0, 0, _n);
  }

 private:
  void add_pt(int u, int a, int b, int A, int B, const pair<int, int>& pt) {
    if (a >= B || A >= b) return;
    if (A <= a && b <= B) {
      _seg[u].push_back(pt);
      return;
    }
    int c = (a + b) >> 1;
    add_pt(2 * u + 1, a, c, A, B, pt);
    add_pt(2 * u + 2, c, b, A, B, pt);
  }
  void dfs(int u, int a, int b) {
    int snapshot = _ds.current_snapshot();
    for (const pair<int, int>& pt : _seg[u]) _ds.merge(pt.first, pt.second);
    if (a + 1 == b) {
      cout << _ds.ans() << " ";
    } else {
      int c = (a + b) >> 1;
      dfs(2 * u + 1, a, c);
      dfs(2 * u + 2, c, b);
    }
    _ds.rollback(snapshot);
  }

 private:
  int _n;
  vector<pair<int, int>> const& _p;
  vector<vector<pair<int, int>>> _seg;
  DS _ds;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> q;
  vector<pair<int, int>> p(q);
  int mx = 0, my = 0;
  for (pair<int, int>& pi : p) {
    cin >> pi.first >> pi.second;
    mx = max(mx, pi.first);
    my = max(my, pi.second);
  }
  Solution(p, mx, my).solve();
  return 0;
}