Suppose you are given a sequence S of k pairs of integers (a_1, b_1), (a_2, b_2), ..., (a_k, b_k).

You can perform the following operations on it:

  1. Choose some position i and increase a_i by 1. That can be performed only if there exists at least one such position j that i ≠ j and a_i = a_j. The cost of this operation is b_i; 
  2. Choose some position i and decrease a_i by 1. That can be performed only if there exists at least one such position j that a_i = a_j + 1. The cost of this operation is -b_i. 



Each operation can be performed arbitrary number of times (possibly zero).

Let f(S) be minimum possible x such that there exists a sequence of operations with total cost x, after which all a_i from S are pairwise distinct. 

Now for the task itself ...

You are given a sequence P consisting of n pairs of integers (a_1, b_1), (a_2, b_2), ..., (a_n, b_n). All b_i are pairwise distinct. Let P_i be the sequence consisting of the first i pairs of P. Your task is to calculate the values of f(P_1), f(P_2), ..., f(P_n).

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of pairs in sequence P.

Next n lines contain the elements of P: i-th of the next n lines contains two integers a_i and b_i (1 ≤ a_i ≤ 2 ⋅ 10^5, 1 ≤ b_i ≤ n). It is guaranteed that all values of b_i are pairwise distinct.

Output

Print n integers — the i-th number should be equal to f(P_i).

Examples

Input

5
1 1
3 3
5 5
4 2
2 4


Output

0
0
0
-5
-16


Input

4
2 4
2 3
2 2
1 1


Output

0
3
7
1
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
const int MAXN = 200010;
const int INF = 1e9;
const int MX = 200002;
int N;
long long sum[MAXN << 5], szt[MAXN << 5], sum2[MAXN << 5];
int ls[MAXN << 5], rs[MAXN << 5];
int fa[MAXN * 2 + 1], mn[MAXN * 2 + 1], root[MAXN * 2 + 1];
long long ans = 0, sumt = 0;
int cnt;
inline void update(int rt) {
  sum[rt] = sum[ls[rt]] + sum[rs[rt]];
  szt[rt] = szt[ls[rt]] + szt[rs[rt]];
  sum2[rt] = sum2[ls[rt]] + sum[ls[rt]] * szt[rs[rt]] + sum2[rs[rt]];
  return;
}
inline void Insert(int &rt, int l, int r, long long k) {
  if (!rt) rt = ++cnt;
  if (l == r) {
    sum[rt] += k;
    szt[rt]++;
    sum2[rt] += szt[rt] * k;
    return;
  }
  int mid = (l + r) >> 1;
  if (k <= mid)
    Insert(ls[rt], l, mid, k);
  else
    Insert(rs[rt], mid + 1, r, k);
  update(rt);
  return;
}
inline int Merge(int x, int y, int l, int r) {
  if (!x || !y) return (x + y);
  int mid = (l + r) >> 1;
  ls[x] = Merge(ls[x], ls[y], l, mid);
  rs[x] = Merge(rs[x], rs[y], mid + 1, r);
  if (l == r) {
    sum2[x] = sum2[x] + szt[x] * sum[y] + sum2[y];
    sum[x] = sum[x] + sum[y];
    szt[x] = szt[x] + szt[y];
  } else
    update(x);
  return x;
}
inline long long calc(int k) {
  return sum2[root[k]] + sum[root[k]] * (mn[k] - 1);
}
inline int find(int x) { return (x == fa[x] ? x : (fa[x] = find(fa[x]))); }
inline void merge(int u, int v) {
  u = find(u);
  v = find(v);
  if (u == v) return;
  ans -= calc(u);
  ans -= calc(v);
  fa[v] = u;
  mn[u] = min(mn[u], mn[v]);
  root[u] = Merge(root[u], root[v], 1, N);
  ans += calc(u);
}
int main() {
  N = read();
  for (int i = 1; i <= 2 * MX; i++) fa[i] = i, mn[i] = i;
  for (int i = 1; i <= N; i++) {
    long long k = read(), v = read();
    sumt += k * v;
    ans -= calc(find(k));
    Insert(root[find(k)], 1, N, v);
    ans += calc(find(k));
    int bel = find(k);
    merge(bel, mn[bel] + szt[root[bel]]);
    printf("%lld\n", ans - sumt);
  }
  return 0;
}
