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 For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 2e5+10;
int n,x[N],y[N],l[N],r[N];
pair<pa,int> a[N];
ll ans[N];

const ll inf = 1e15;
map<int,ll>dp[2][N];
inline ll dis(pa a,pa b){
	return abs(x[a.fi]-x[b.fi])+abs(y[a.se]-y[b.se]);
}
inline ll dfs(int l,int r,bool k,int mn,int mx){
	if (dp[k][l].count(r)) return dp[k][l][r];
	ll ans=inf;
	int L=::l[l-1],R=::r[r+1];
	if (l>1&&(a[l-1].fi.se==mn-1||a[l-1].fi.se==mx+1)){
		ans=min(ans,dfs(L,r,0,min(mn,a[L].fi.se),max(mx,a[L].fi.se))+dis(!k?a[l].fi:a[r].fi,a[L].fi));
	}
	if (r<n&&(a[r+1].fi.se==mn-1||a[r+1].fi.se==mx+1)){
		ans=min(ans,dfs(l,R,1,min(mn,a[R].fi.se),max(mx,a[R].fi.se))+dis(!k?a[l].fi:a[r].fi,a[R].fi));
	}
	return dp[k][l][r]=(ans==inf?l-r:ans);
}

int main(){
	n=read();
	For(i,1,n) x[i]=read(),y[i]=read(),a[i]={{x[i],y[i]},i};
	sort(a+1,a+1+n),sort(x+1,x+1+n),sort(y+1,y+1+n);
	For(i,1,n){
		a[i].fi.fi=lower_bound(x+1,x+1+n,a[i].fi.fi)-x;
		a[i].fi.se=lower_bound(y+1,y+1+n,a[i].fi.se)-y;
	}
	l[1]=1;
	For(i,2,n){
		if (abs(a[i].fi.se-a[i-1].fi.se)==1) l[i]=l[i-1];
			else l[i]=i;
	}
	r[n]=n;
	Dow(i,n-1,1)
		if (abs(a[i].fi.se-a[i+1].fi.se)==1) r[i]=r[i+1];
			else r[i]=i;
	For(i,1,n) ans[a[i].se]=dfs(i,i,0,a[i].fi.se,a[i].fi.se);
	For(i,1,n) printf("%lld\n",ans[i]);
}