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;
constexpr int MAXM = 300000;
struct Dsu {
  struct node_struct {
    int par, size;
    long long sz, w, h;
    node_struct(int p, int s) : par(p), size(s) {
      w = p < MAXM, h = p >= MAXM;
      sz = w * h;
    }
    void merge(node_struct& b) {
      b.par = par;
      size += b.size;
      w += b.w;
      h += b.h;
      sz = w * h;
    }
  };
  vector<node_struct> nodes;
  long long ans = 0;
  stack<long long> ans_stk;
  stack<tuple<int, int, node_struct, node_struct>> stk;
  Dsu(int n = 2 * MAXM) {
    nodes.reserve(n);
    for (int i = 0; i < n; ++i) nodes.emplace_back(i, 1);
  }
  int anc(int x) {
    while (x != nodes[x].par) x = nodes[x].par;
    return x;
  }
  bool unite(int x, int y) {
    int a = anc(x);
    int b = anc(y);
    stk.emplace(a, b, nodes[a], nodes[b]);
    ans_stk.push(ans);
    if (a == b) return false;
    ans -= nodes[a].sz + nodes[b].sz;
    if (nodes[a].size < nodes[b].size) swap(a, b);
    nodes[a].merge(nodes[b]);
    ans += nodes[a].sz;
    return true;
  }
  void revert(int version = -1) {
    if (version == -1) version = stk.size() - 1;
    for (; stk.size() != version; stk.pop(), ans_stk.pop()) {
      nodes[get<0>(stk.top())] = get<2>(stk.top());
      nodes[get<1>(stk.top())] = get<3>(stk.top());
      ans = ans_stk.top();
    }
  }
};
Dsu djs;
class Seg {
  vector<pair<int, int>> tag;
  int l, m, r;
  Seg* ch[2];

 public:
  Seg(int l, int r) : l(l), r(r), m(l + r >> 1) {
    if (r - l > 1) {
      ch[0] = new Seg(l, m);
      ch[1] = new Seg(m, r);
    }
  }
  void add_tag(int ql, int qr, pair<int, int> v) {
    if (ql <= l and r <= qr) {
      tag.push_back(v);
    } else {
      if (ql < m) ch[0]->add_tag(ql, qr, v);
      if (m < qr) ch[1]->add_tag(ql, qr, v);
    }
  }
  void dfs(vector<long long>& buff) {
    for (auto P : tag) {
      int x, y;
      tie(x, y) = P;
      djs.unite(x, y + MAXM);
    }
    if (r - l == 1)
      buff.push_back(djs.ans);
    else
      ch[0]->dfs(buff), ch[1]->dfs(buff);
    for (int i = 0; i < tag.size(); ++i) {
      djs.revert();
    }
  }
};
class Solution {
  int q;

 public:
  void run() {
    cin >> q;
    Seg root(0, q);
    map<pair<int, int>, int> prev;
    for (int i = 0; i < q; ++i) {
      int x, y;
      cin >> x >> y;
      --x, --y;
      if (prev.count({x, y})) {
        root.add_tag(prev[{x, y}], i, {x, y});
        prev.erase({x, y});
      } else
        prev[{x, y}] = i;
    }
    vector<long long> ans;
    for (auto P : prev) root.add_tag(P.second, q, P.first);
    root.dfs(ans);
    for (int i = 0; i < q; ++i) cout << ans[i] << " \n"[i == q - 1];
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  Solution().run();
}
