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>
#pragma GCC optimize(2)
#pragma warning(disable : 4996)
using namespace std;
namespace Bigcat {
template <typename T>
inline void max_s(T& a, const T& b) {
  a = max(a, b);
}
template <typename T>
inline void min_s(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void sort_v(T& x) {
  sort(x.begin(), x.end());
}
template <typename T>
void erase_dup(T& x) {
  x.erase(unique(x.begin(), x.end()), x.end());
}
template <typename T, typename V>
int pos_l(const T& x, const V& v) {
  return lower_bound(x.begin(), x.end(), v) - x.begin();
}
template <typename T, typename V>
int pos_u(const T& x, const V& v) {
  return upper_bound(x.begin(), x.end(), v) - x.begin();
}
inline unsigned rand_g() {
  static mt19937 mt_rand((int)time(0));
  return mt_rand();
}
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using PII = pair<int, int>;
using VPII = vector<PII>;
}  // namespace Bigcat
using namespace Bigcat;
const LL base = LL(1e9 + 7);
const LL INFL = 1LL << 62;
const int INF = 1 << 30;
const int MAX = int(3e5 + 100);
struct Node {
  int x, y, l, r;
};
bool operator<(const Node& n0, const Node& n1) { return n0.x < n1.y; }
int dsu[MAX * 2];
int s0[MAX * 2];
int s1[MAX * 2];
LL result = 0;
int findr(int v) {
  while (dsu[v] != v) v = dsu[v];
  return v;
}
inline LL getm(int v) { return LL(s0[v]) * s1[v]; }
PII uni(int x, int y) {
  y += MAX;
  x = findr(x);
  y = findr(y);
  if (x == y) return {-1, -1};
  if (s0[x] + s1[x] > s0[y] + s1[y]) {
    swap(x, y);
  }
  result -= getm(x);
  result -= getm(y);
  dsu[x] = y;
  s0[y] += s0[x];
  s1[y] += s1[x];
  result += getm(y);
  return {x, y};
}
void restore(const VPII& oper_list) {
  for (int i = oper_list.size() - 1; i >= 0; --i) {
    int x, y;
    x = oper_list[i].first;
    y = oper_list[i].second;
    result -= getm(y);
    assert(dsu[y] == y);
    assert(dsu[x] == y);
    s0[y] -= s0[x];
    s1[y] -= s1[x];
    result += getm(x);
    result += getm(y);
    dsu[x] = x;
  }
}
void work(int l0, int u0, vector<Node>& zq) {
  vector<Node> z0, z1;
  int mid = (l0 + u0) / 2;
  VPII oper_list;
  LL tresult = result;
  for (auto& x : zq) {
    if (x.r < l0 || u0 < x.l) continue;
    if (x.l <= l0 && u0 <= x.r) {
      auto t = uni(x.x, x.y);
      if (t.first >= 0) {
        oper_list.push_back(t);
      }
    } else {
      if (x.l <= mid) z0.push_back(x);
      if (mid < x.r) z1.push_back(x);
    }
  }
  if (l0 == u0) {
    cout << result << ' ';
  } else {
    work(l0, mid, z0);
    work(mid + 1, u0, z1);
  }
  restore(oper_list);
  assert(result == tresult);
}
void solve1() {
  int n;
  for (int i = 0; i < (int)(MAX * 2); i++) {
    dsu[i] = i;
  }
  for (int i = 0; i < (int)(MAX); i++) {
    s0[i] = 1;
    s1[i + MAX] = 1;
  }
  cin >> n;
  vector<Node> zq;
  map<PII, int> pool;
  for (int i = 0; i < (int)(n); i++) {
    int x, y;
    cin >> x >> y;
    PII t = {x, y};
    if (pool.count(t) > 0) {
      zq.push_back({t.first, t.second, pool[t], i - 1});
      pool.erase(t);
    } else {
      pool[t] = i;
    }
  }
  for (auto x : pool) {
    auto t = x.first;
    int b = x.second;
    zq.push_back({t.first, t.second, b, n});
  }
  work(0, n - 1, zq);
  assert(result == 0);
}
void solve() {
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve1();
  }
  int x = 1;
}
void io_init() {
  const int inId = 1;
  const int outId = 0;
  if (inId > 0) {
    cerr << "redirect stdin to input " << inId << endl;
    string s = "input";
    s += to_string(inId);
    s += ".txt";
    auto r = freopen(s.c_str(), "r", stdin);
    if (r == nullptr) {
      cerr << "invalid input file " << s << endl;
      ;
      r = freopen("CON", "r", stdin);
    }
  }
  if (outId > 0) {
    cerr << "redirect stdout to stdout " << outId << endl;
    string s = "stdout";
    s += to_string(outId);
    s += ".txt";
    auto r = freopen(s.c_str(), "w", stdout);
    if (r == nullptr) {
      cerr << "invalid output file " << s << endl;
      ;
      r = freopen("CON", "w", stdout);
    }
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.precision(11);
  solve();
}
