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< int >options;
    if (l > 1 && (p[l-1]==mn-1||p[l-1]==mx+1)) {
        options.push_back(0);
    }
    if (r < n && (p[r+1]==mn-1||p[r+1]==mx+1)) {
        options.push_back(1);
    }

    LL ans = 0;
    if (options.size() == 0) {
        ans = l-r;
    } else if (options.size() == 1) {
        if (options[0] == 0) {
            int _l = bam[l-1];
            ans = solve(_l, r, false, min(mn, p[_l]), max(mx, p[_l]));
            ans += (side ? durotto(r, _l) : durotto(l, _l));
        } else {
            int _r = dan[r+1];
            ans = solve(l, _r, true, min(mn, p[_r]), max(mx, p[_r]));
            ans += (side ? durotto(r, _r) : durotto(l, _r));
        }
    } else if (options.size() == 2) {
        ans = 1e15;
        int _l = bam[l-1];
        int _r = dan[r+1];
        int _mn = min(mn, min(p[_l], p[_r]));
        int _mx = max(mx, max(p[_l], p[_r]));
        {
            LL tmp = solve(_l, _r, true, _mn, _mx);
            if (side) {
                tmp += durotto(r, _l)*2+durotto(r, _r);
            } else {
                tmp += durotto(l, _l)*2+durotto(l, _r);
            }
            ans = min(ans, tmp);
        }
        {
            LL tmp = solve(_l, _r, false, _mn, _mx);
            if (side) {
                tmp += durotto(r, _r)*2+durotto(r, _l);
            } else {
                tmp += durotto(l, _r)*2+durotto(l, _l);
            }
            ans = min(ans, tmp);
        }
    }

//    counter++;
//    cout << options.size() << " options" << endl;
//    cout << "dp[" << side << "][" << l << "][" << r << "] = " << ans << endl;
    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;
//        cout << "q[" << idY[i] << "] = " << i+1 << endl;
    }
    for (int i = 1; i <= n; i++) {
        p[i] = q[idX[i]];
//        cout << p[i] << " ";
    }
//    cout << endl;

    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;
}