Problem: You are given positions (X_i, Y_i) of N enemy rooks on an infinite chessboard. No two rooks attack each other (at most one rook per row or column).

You're going to replace one rook with a king and then move the king repeatedly to beat as many rooks as possible.

You can't enter a cell that is being attacked by a rook. Additionally, you can't move diagonally to an empty cell (but you can beat a rook diagonally).

(So this king moves like a superpawn that beats diagonally in 4 directions and moves horizontally/vertically in 4 directions.)

For each rook, consider replacing it with a king, and find the minimum possible number of moves needed to beat the maximum possible number of rooks.

Constraints

* 2 \leq N \leq 200\,000
* 1 \leq X_i, Y_i \leq 10^6
* X_i \neq X_j
* Y_i \neq Y_j
* All values in input are integers.

Input

Input is given from Standard Input in the following format.


N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N


Output

Print N lines. The i-th line is for scenario of replacing the rook at (X_i, Y_i) with your king. This line should contain one integer: the minimum number of moves to beat M_i rooks where M_i denotes the maximum possible number of beaten rooks in this scenario (in infinite time).

Examples

Input

6
1 8
6 10
2 7
4 4
9 3
5 1


Output

5
0
7
5
0
0


Input

5
5 5
100 100
70 20
81 70
800 1


Output

985
985
1065
1034
0


Input

10
2 5
4 4
13 12
12 13
14 17
17 19
22 22
16 18
19 27
25 26


Output

2
2
9
9
3
3
24
5
0
25

Solution (in CPP):

Solution:
/**
 *    author:  tourist
 *    created: 09.08.2020 16:54:47       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  auto old_x = x;
  auto old_y = y;
  sort(x.begin(), x.end());
  sort(y.begin(), y.end());
  vector<int> p(n);
  vector<int> id(n);
  for (int i = 0; i < n; i++) {
    int j = (int) (lower_bound(x.begin(), x.end(), old_x[i]) - x.begin());
    int k = (int) (lower_bound(y.begin(), y.end(), old_y[i]) - y.begin());
    p[j] = k;
    id[j] = i;
  }
  auto Dist = [&](int i, int j) {
    return abs(x[i] - x[j]) + abs(y[p[i]] - y[p[j]]);
  };
  vector<long long> ans(n);
  int beg = 0;
  while (beg < n) {
    int end = beg;
    while (end + 1 < n && abs(p[end] - p[end + 1]) == 1) {
      ++end;
    }
    int from = beg;
    int to = end;
    int mn = min(p[beg], p[end]);
    int mx = max(p[beg], p[end]);
    vector<tuple<int, int, int, int>> segs;
    segs.emplace_back(from, to, mn, mx);
    while (true) {
      if (from > 0 && p[from - 1] == mn - 1 && to < n - 1 && p[to + 1] == mx + 1) {
        while (from > 0 && p[from - 1] == mn - 1) {
          --mn;
          --from;
        }
        while (to < n - 1 && p[to + 1] == mx + 1) {
          ++mx;
          ++to;
        }
        segs.emplace_back(from, to, mn, mx);
        continue;
      }
      if (from > 0 && p[from - 1] == mx + 1 && to < n - 1 && p[to + 1] == mn - 1) {
        while (from > 0 && p[from - 1] == mx + 1) {
          ++mx;
          --from;
        }
        while (to < n - 1 && p[to + 1] == mn - 1) {
          --mn;
          ++to;
        }
        segs.emplace_back(from, to, mn, mx);
        continue;
      }
      if (from > 0 && p[from - 1] == mn - 1) {
        while (from > 0 && p[from - 1] == mn - 1) {
          --mn;
          --from;
        }
        segs.emplace_back(from, to, mn, mx);
        continue;
      }
      if (from > 0 && p[from - 1] == mx + 1) {
        while (from > 0 && p[from - 1] == mx + 1) {
          ++mx;
          --from;
        }
        segs.emplace_back(from, to, mn, mx);
        continue;
      }
      if (to < n - 1 && p[to + 1] == mn - 1) {
        while (to < n - 1 && p[to + 1] == mn - 1) {
          --mn;
          ++to;
        }
        segs.emplace_back(from, to, mn, mx);
        continue;
      }
      if (to < n - 1 && p[to + 1] == mx + 1) {
        while (to < n - 1 && p[to + 1] == mx + 1) {
          ++mx;
          ++to;
        }
        segs.emplace_back(from, to, mn, mx);
        continue;
      }
      break;
    }
    int rooks = to - from + 1;
    reverse(segs.begin(), segs.end());
    long long L = 0;
    long long R = 0;
    for (int i = 1; i < (int) segs.size(); i++) {
      int from = get<0>(segs[i]);
      int to = get<1>(segs[i]);
      int mn = get<2>(segs[i]);
      int mx = get<3>(segs[i]);
      int big_from = get<0>(segs[i - 1]);
      int big_to = get<1>(segs[i - 1]);
      int big_mn = get<2>(segs[i - 1]);
      int big_mx = get<3>(segs[i - 1]);
      if (from == big_from) {
        long long newL = Dist(from, big_to) + R;
        long long newR = Dist(to, big_to) + R;
        L = newL;
        R = newR;
        continue;
      }
      if (to == big_to) {
        long long newL = Dist(big_from, from) + L;
        long long newR = Dist(big_from, to) + L;
        L = newL;
        R = newR;
        continue;
      }
      long long newL = min(Dist(from, big_to) + Dist(big_to, big_from) + L,
                           Dist(from, big_from) + Dist(big_from, big_to) + R);
      long long newR = min(Dist(  to, big_to) + Dist(big_to, big_from) + L,
                           Dist(  to, big_from) + Dist(big_from, big_to) + R);
      L = newL;
      R = newR;
    }
    for (int i = beg; i <= end; i++) {
      ans[id[i]] = min(Dist(i, beg) + Dist(beg, end) + R, Dist(i, end) + Dist(end, beg) + L) - (rooks - 1);
    }
    beg = end + 1;
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}