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>
using namespace std;
typedef long long LL;
const int MAXN = 2e5+7;
//const int MAXN = 1e3+7;

int X[MAXN], Y[MAXN];
int idX[MAXN];

int p[MAXN], q[MAXN];
int bam[MAXN], dan[MAXN];
int n;

int durotto(int i, int j) {
    i = idX[i];
    j = idX[j];
    return abs(X[i]-X[j])+abs(Y[i]-Y[j]);
}

int counter;
map< int , LL >dp[2][MAXN];
LL solve(int l, int r, bool side, int mn, int mx) {
    auto it = dp[side][l].find(r);
    if (it != dp[side][l].end()) return it->second;

    vector< LL >options;
    if (l > 1 && (p[l-1]==mn-1||p[l-1]==mx+1)) {
        LL tmp = solve(bam[l-1], r, false, min(mn, p[bam[l-1]]), max(mx, p[bam[l-1]]));
        tmp += (side ? durotto(bam[l-1], r) : durotto(bam[l-1], l));
        options.push_back(tmp);
    }
    if (r < n && (p[r+1]==mn-1||p[r+1]==mx+1)) {
        LL tmp = solve(l, dan[r+1], true, min(mn, p[dan[r+1]]), max(mx, p[dan[r+1]]));
        tmp += (side ? durotto(r, dan[r+1]) : durotto(l, dan[r+1]));
        options.push_back(tmp);
    }
    LL ans = l-r;
    if (options.size() >= 1) {
        ans = options.front();
        if (options.size() >= 2) {
            ans = min(ans, options[1]);
        }
    }
    counter++;
    return dp[side][l][r] = ans;
}

LL ans[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    vector< int >idY(n, 0);
    for (int i = 1; i <= n; i++) {
        cin >> X[i] >> Y[i];
        idX[i] = i;
        idY[i-1] = i;
    }

    sort(idX+1, idX+n+1, [&](int i, int j) {
        return X[i] < X[j];
    });
    sort(idY.begin(), idY.end(), [&](int i, int j) {
        return Y[i] < Y[j];
    });
    for (int i = 0; i < n; i++) {
        q[idY[i]] = i+1;
    }
    for (int i = 1; i <= n; i++) {
        p[i] = q[idX[i]];
    }

    bam[1] = 1;
    for (int i = 2; i <= n; i++) {
        bam[i] = i;
        if (abs(p[i]-p[i-1])==1) bam[i] = bam[i-1];
    }
    dan[n] = n;
    for (int i = n-1; i > 0; i--) {
        dan[i] = i;
        if (abs(p[i]-p[i+1])==1) dan[i] = dan[i+1];
    }

    for (int i = 1; i <= n; i++) {
        ans[idX[i]] = solve(i, i, false, p[i], p[i]);
    }

//    cout << "counter: " << counter << endl;
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}