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;
const int N = (int)1e6 + 3;
struct query {
  int l, r, x, y;
};
template <class T>
struct HistoryArray {
  vector<T> arr;
  vector<T> prevVal;
  vector<int> prevPos;
  vector<int> prevVersion;
  int curVersion;
  HistoryArray() : curVersion(0) {}
  HistoryArray(int n, T val) : curVersion(0) { arr.assign(n, val); }
  void Set(int x, T val) {
    prevVal.push_back(arr[x]);
    prevPos.push_back(x);
    prevVersion.push_back(curVersion);
    curVersion++;
    arr[x] = val;
  }
  T Get(int x) { return arr[x]; }
  int GetVersion() { return curVersion; }
  void RestoreTo(int version) {
    for (; !(prevVersion.empty() || prevVersion.back() < version);) {
      arr[prevPos.back()] = prevVal.back();
      prevVersion.pop_back();
      prevVal.pop_back();
      prevPos.pop_back();
    }
  }
};
struct dsu {
  int ySplit;
  HistoryArray<int> p;
  HistoryArray<int> cntX, cntY;
  HistoryArray<long long> answer;
  dsu() {}
  dsu(int n, int ySplit)
      : ySplit(ySplit), p(n, -1), cntX(n, 0), cntY(n, 0), answer(1, 0) {
    for (int(i) = (0); (i) < (n); (i)++) {
      if (i < ySplit) {
        cntX.Set(i, 1);
      } else {
        cntY.Set(i, 1);
      }
    }
  }
  int Get(int x) {
    if (p.Get(x) == -1) return x;
    int ans = Get(p.Get(x));
    p.Set(x, ans);
    return ans;
  }
  void Union(int a, int b) {
    a = Get(a);
    b = Get(b);
    if (a == b) return;
    int par, child;
    if (rand() % 2 == 0) {
      par = a;
      child = b;
    } else {
      par = b;
      child = a;
    }
    long long newAns = answer.Get(0);
    newAns -= CalcAnswer(child);
    newAns -= CalcAnswer(par);
    p.Set(child, par);
    cntX.Set(par, cntX.Get(par) + cntX.Get(child));
    cntY.Set(par, cntY.Get(par) + cntY.Get(child));
    newAns += CalcAnswer(par);
    answer.Set(0, newAns);
  }
  long long CalcAnswer(int a) {
    a = Get(a);
    return (long long)cntX.Get(a) * cntY.Get(a);
  }
  long long GetAnswer() { return answer.Get(0); }
  tuple<int, int, int, int> GetVersion() {
    return make_tuple(p.GetVersion(), cntX.GetVersion(), cntY.GetVersion(),
                      answer.GetVersion());
  }
  void RestoreTo(const tuple<int, int, int, int>& version) {
    p.RestoreTo(get<0>(version));
    cntX.RestoreTo(get<1>(version));
    cntY.RestoreTo(get<2>(version));
    answer.RestoreTo(get<3>(version));
  }
};
dsu d;
map<int, int> xToInt, yToInt;
void Rec(const vector<query>& queries, int l, int r) {
  if (l > r) return;
  auto version = d.GetVersion();
  if (l == r) {
    for (auto& e : queries) {
      if (e.l <= l && r <= e.r) {
        d.Union(xToInt[e.x], yToInt[e.y]);
      }
    }
    printf("%lld ", d.GetAnswer());
  } else {
    auto version = d.GetVersion();
    vector<query> queries2;
    for (auto& e : queries) {
      if (e.l <= l && r <= e.r) {
        d.Union(xToInt[e.x], yToInt[e.y]);
      } else if (!(r < e.l || e.r < l)) {
        queries2.push_back(e);
      }
    }
    int m = (l + r) / 2;
    Rec(queries2, l, m);
    Rec(queries2, m + 1, r);
  }
  d.RestoreTo(version);
}
int main(int argc, char* argv[]) {
  ios::sync_with_stdio(0);
  vector<query> queries;
  int n;
  cin >> n;
  map<pair<int, int>, int> start;
  for (int(i) = (0); (i) < (n); (i)++) {
    int x, y;
    cin >> x >> y;
    if (start.count(make_pair(x, y))) {
      queries.push_back({start[make_pair(x, y)], i - 1, x, y});
      start.erase(make_pair(x, y));
    } else {
      start[make_pair(x, y)] = i;
    }
  }
  for (auto it = start.begin(); it != start.end(); ++it) {
    queries.push_back({it->second, n, it->first.first, it->first.second});
  }
  for (int(i) = (0); (i) < ((int((queries).size()))); (i)++) {
    xToInt[queries[i].x];
    yToInt[queries[i].y];
  }
  int nVerts = 0;
  for (auto& k : xToInt) {
    k.second = nVerts++;
  }
  for (auto& k : yToInt) {
    k.second = nVerts++;
  }
  d = dsu(nVerts, (int((xToInt).size())));
  Rec(queries, 0, n - 1);
  return 0;
}