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:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; --i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
//using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;

struct P {
    int i;
    int x;
    int y;
    int yrank;};

ll dist(P a, P b) {return abs(a.x - b.x) + abs(a.y - b.y);}

vector<int> ld, lu, rd, ru;
int n;
vector<P> p;
map<tuple<int, int, int>, ll> memo1, memo2;
ll f2(int i, int L, int R, int yl, int yu);

ll f1(int i, int L, int R, int yl, int yu) {
    if (memo1.count({i, L, R}) > 0) return memo1[{i, L, R}];
    // [L, R] * [yl, yu] is available
    bool ok_l = L-1 >= 0 && p[L-1].yrank == yl - 1, 
         ok_r = R+1 < n && p[R+1].yrank == yu + 1;
    ll ret;
    if (!ok_l && !ok_r) {
        ret = f2(i, L, R, yl, yu);
    } else if (!ok_r) {
        int nl = ld[L-1];
        ret = dist(p[i], p[nl]) - (L - nl) + f2(nl, nl, R, p[nl].yrank, yu);
    } else if (!ok_l) {
        int nr = ru[R+1];
        ret = dist(p[i], p[nr]) - (nr - R) + f2(nr, L, nr, yl, p[nr].yrank);
    } else {
        int nl = ld[L-1];
        int nr = ru[R+1];
        ret = min(dist(p[i], p[nr]) + dist(p[nr], p[nl]) - (L - nl + nr - R) + f2(nl, nl, nr, p[nl].yrank, p[nr].yrank),
                  dist(p[i], p[nl]) + dist(p[nl], p[nr]) - (L - nl + nr - R) + f2(nr, nl, nr, p[nl].yrank, p[nr].yrank));
    }
    return memo1[{i, L, R}] = ret;
}

ll f2(int i, int L, int R, int yl, int yu) {
    if (memo2.count({i, L, R}) > 0) return memo2[{i, L, R}];
    // [L, R] * [yl, yu] is available
    bool ok_l = L-1 >= 0 && p[L-1].yrank == yu + 1, 
         ok_r = R+1 < n && p[R+1].yrank == yl - 1;
    ll ret;
    if (!ok_l && !ok_r) {
        ret = 0;
    } else if (!ok_r) {
        int nl = lu[L-1];
        ret = dist(p[i], p[nl]) - (L - nl) + f1(nl, nl, R, yl, p[nl].yrank);
    } else if (!ok_l) {
        int nr = rd[R+1];
        ret = dist(p[i], p[nr]) - (nr - R) + f1(nr, L, nr, p[nr].yrank, yu);
    } else {
        int nl = lu[L-1];
        int nr = rd[R+1];
        ret = min(dist(p[i], p[nr]) + dist(p[nr], p[nl]) - (L - nl + nr - R) + f1(nl, nl, nr, p[nr].yrank, p[nl].yrank),
                  dist(p[i], p[nl]) + dist(p[nl], p[nr]) - (L - nl + nr - R) + f1(nr, nl, nr, p[nr].yrank, p[nl].yrank));
    }
    return memo2[{i, L, R}] = ret;
}


int main() {
    cin >> n;
    p = vector<P>(n);
    ld = vector<int>(n); 
    lu = vector<int>(n); 
    rd = vector<int>(n); 
    ru = vector<int>(n); 
    rep(i, n) {
        cin >> p[i].x >> p[i].y;
        p[i].i = i;
    }
    sort(all(p), [](P a, P b) {return a.y < b.y;});
    rep(i, n) p[i].yrank = i;
    sort(all(p), [](P a, P b) {return a.x < b.x;});
    {
        int pre = -2, cur = -1;
        rep(i, n) {
            if (pre + 1 != p[i].yrank) cur = i;
            ld[i] = cur;
            pre = p[i].yrank;
        }
    }
    {
        int pre = -2, cur = -1;
        rep(i, n) {
            if (pre - 1 != p[i].yrank) cur = i;
            lu[i] = cur;
            pre = p[i].yrank;
        }
    }
    {
        int pre = -2, cur = -1;
        rrep(i, n) {
            if (pre + 1 != p[i].yrank) cur = i;
            rd[i] = cur;
            pre = p[i].yrank;
        }
    }
    {
        int pre = -2, cur = -1;
        rrep(i, n) {
            if (pre - 1 != p[i].yrank) cur = i;
            ru[i] = cur;
            pre = p[i].yrank;
        }
    }

    vector<ll> ans(n);
    rep(i, n) {
        ll a = f1(i, i, i, p[i].yrank, p[i].yrank);
        ans[p[i].i] = a;
    }
    rep(i, n) cout << ans[i] << endl;
}