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;
#pragma warning(disable : 4996)
const int N = 1 << 19;
using pa = pair<int, int>;
struct UnionFind {
  using Value = pair<int, int>;
  Value INI = make_pair(-1, -1);
  vector<Value> data;
  stack<pair<int, pair<int, int>>> sta;
  UnionFind(int size) : data(size, INI) {}
  bool unionSet(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      sta.push(make_pair(y, data[y]));
      data[x].first += data[y].first;
      data[x].second += data[y].second;
      data[y] = make_pair(x, x);
    } else {
      sta.push(make_pair(-7777777, make_pair(-1, -1)));
    }
    return x != y;
  }
  void roll_back() {
    assert(!sta.empty());
    auto p = sta.top();
    sta.pop();
    if (p.first == -7777777) return;
    int y = p.first;
    pair<int, int> y_sz = p.second;
    int x = root(y);
    data[x].first -= y_sz.first;
    data[x].second -= y_sz.second;
    data[y] = y_sz;
  }
  int root(int x) {
    if (data[x].first + data[x].second < 0) {
      return x;
    } else {
      int ro = root(data[x].first);
      return ro;
    }
  }
  pair<int, int> size(int x) {
    return make_pair(-data[root(x)].first, -data[root(x)].second);
  }
};
vector<vector<pa>> pas(4 * N);
void update(int l, int r, int a, int b, int id, pa apa) {
  if (a <= l && r <= b) {
    pas[id].push_back(apa);
  } else if (r <= a || b <= l) {
  } else {
    int m((l + r) / 2);
    update(l, m, a, b, id * 2 + 1, apa);
    update(m, r, a, b, id * 2 + 2, apa);
  }
}
void ad(long long int& ans, pair<long long int, long long int> p) {
  ans += p.first * p.second;
}
void mi(long long int& ans, pair<long long int, long long int> p) {
  ans -= p.first * p.second;
}
void dfs(long long int& ans, int l, int r, int id,
         vector<long long int>& answers, UnionFind& uf) {
  int num = 0;
  vector<pair<int, int>> ps;
  if (id == 65) {
  }
  for (auto pa : pas[id]) {
    if (uf.root(pa.first) == uf.root(pa.second)) {
    } else {
      int x = uf.root(pa.first);
      int y = uf.root(pa.second);
      if (uf.data[x].first < uf.data[y].first) swap(x, y);
      num++;
      ps.emplace_back(x, y);
      mi(ans, uf.size(x));
      mi(ans, uf.size(y));
      uf.unionSet(x, y);
      ad(ans, uf.size(x));
    }
  }
  if (l + 1 == r) {
    int num = id - 2 * N + 1;
    if (num < answers.size()) {
      answers[id - 2 * N + 1] = ans;
    }
  } else {
    int m = ((l + r) / 2);
    dfs(ans, l, m, id * 2 + 1, answers, uf);
    dfs(ans, m, r, id * 2 + 2, answers, uf);
  }
  if (id == 65) {
  }
  for (int i = ps.size() - 1; i >= 0; --i) {
    auto pp = ps[i];
    mi(ans, uf.size(pp.first));
    uf.roll_back();
    ad(ans, uf.size(pp.first));
    ad(ans, uf.size(pp.second));
  }
}
void test() {
  UnionFind uf(10);
  for (int i = 0; i < 5; ++i) {
    uf.data[i] = make_pair(-1, 0);
    uf.data[5 + i] = make_pair(0, -1);
  }
  while (true) {
    int a, b;
    cin >> a >> b;
    if (a == -1) {
      uf.roll_back();
    } else {
      uf.unionSet(a, b);
    }
    cout << endl << "--begin--" << endl;
    for (int i = 0; i < 10; ++i) {
      cout << uf.data[i].first << " " << uf.data[i].second << endl;
    }
    cout << "--end--" << endl << endl;
  }
}
int main() {
  int Q;
  cin >> Q;
  map<pair<int, int>, int> mp;
  for (int i = 0; i < Q; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--;
    b--;
    pair<int, int> p(a, b + N);
    if (mp.find(p) == mp.end()) {
      mp[p] = i;
    } else {
      update(0, 2 * N, mp[p], i, 0, p);
      mp.erase(p);
    }
  }
  for (auto m : mp) update(0, 2 * N, m.second, Q, 0, m.first);
  vector<long long int> answers(Q);
  UnionFind uf(2 * N);
  for (int i = 0; i < N; ++i) {
    uf.data[i] = make_pair(-1, 0);
    uf.data[N + i] = make_pair(0, -1);
  }
  long long int ans = 0;
  dfs(ans, 0, 2 * N, 0, answers, uf);
  for (int i = 0; i < Q; ++i) {
    printf("%lld ", answers[i]);
  }
  return 0;
}