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;
typedef struct _Query {
  int from, to, leftPt, rightPt;
} Query;
vector<Query> que;
map<pair<int, int>, vector<pair<int, int> > > mp;
long long int ans[300010], val;
int parent[300010 << 1], siz[2][300010 << 1], qNum;
stack<pair<int *, int> > stk;
int getParent(int cntPt) {
  if (parent[cntPt] == cntPt) return cntPt;
  return getParent(parent[cntPt]);
}
bool merge(int fstPt, int sndPt) {
  fstPt = getParent(fstPt), sndPt = getParent(sndPt);
  if (fstPt == sndPt) return false;
  if (siz[0][fstPt] + siz[1][fstPt] < siz[0][sndPt] + siz[1][fstPt])
    swap(fstPt, sndPt);
  stk.push(make_pair(parent + sndPt, parent[sndPt]));
  parent[sndPt] = fstPt;
  for (int t = 0; t < 2; t++) {
    stk.push(make_pair(siz[t] + fstPt, siz[t][fstPt]));
    siz[t][fstPt] += siz[t][sndPt];
  }
  return true;
}
void undo() {
  if (stk.empty()) return;
  *stk.top().first = stk.top().second;
  stk.pop();
}
void divideConquer(int leftPt, int rightPt, const vector<Query> &vec) {
  int midPt = (leftPt + rightPt) >> 1, stkSiz = stk.size();
  long long int prev = val;
  vector<Query> leftVec, rightVec;
  for (const auto &q : vec) {
    if (q.leftPt == leftPt && q.rightPt == rightPt) {
      int from = getParent(q.from << 1), to = getParent(q.to << 1 | 1);
      if (from == to) continue;
      val -= 1ll * siz[0][from] * siz[1][from] + 1ll * siz[0][to] * siz[1][to];
      merge((q.from << 1), (q.to << 1 | 1));
      from = getParent(q.from << 1);
      val += 1ll * siz[0][from] * siz[1][from];
    } else {
      if (q.leftPt <= midPt)
        leftVec.push_back(Query{q.from, q.to, q.leftPt, min(q.rightPt, midPt)});
      if (q.rightPt > midPt)
        rightVec.push_back(
            Query{q.from, q.to, max(q.leftPt, midPt + 1), q.rightPt});
    }
  }
  if (leftPt == rightPt) {
    ans[leftPt] = val;
    while ((int)stk.size() != stkSiz) undo();
    val = prev;
    return;
  }
  divideConquer(leftPt, midPt, leftVec);
  divideConquer(midPt + 1, rightPt, rightVec);
  while ((int)stk.size() != stkSiz) undo();
  val = prev;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int len;
  qNum = 0;
  val = 0;
  cin >> len;
  for (int i = 0; i < (300010 << 1); i++)
    parent[i] = i, siz[i & 1][i] = 1, siz[(i & 1) ^ 1][i] = 0;
  for (int i = 0; i < len; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    auto &v = mp[make_pair(x, y)];
    if (v.size() == 0 || v.back().second != len - 1)
      v.push_back(make_pair(i, len - 1));
    else
      v.back().second = i - 1;
  }
  for (const auto &p : mp)
    for (const auto &p1 : p.second)
      que.push_back({p.first.first, p.first.second, p1.first, p1.second});
  divideConquer(0, len - 1, que);
  for (int i = 0; i < len; i++) cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}
