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<cstdio>
#include<vector>
const long long inf=1ll<<60;
int N,MX,MY,id[1000010],Y[1000010],rk_Y[1000010];
struct Point{int i,x,y;}P[200010];
int diff(int x,int y){return x>y?x-y:y-x;}
int dist(Point*p,Point*q){return diff(p->x,q->x)+diff(p->y,q->y);}
void cmin(int&x,int y){y<x?x=y:1;}
void cmax(int&x,int y){y>x?x=y:1;}
int pre_len[200010]; 
long long ans[200010];
int main(){
	scanf("%d",&N);
	for(int i=0,x,y;i<N;i++){
		scanf("%d%d",&x,&y);
		id[x]=i;Y[x]=y;rk_Y[y]++;
		cmax(MX,x);cmax(MY,y);
	}
	for(int i=1;i<=MY;i++)rk_Y[i]+=rk_Y[i-1];
	for(int x=1,n=0;x<=MX;x++)if(Y[x])P[n++]=(Point){id[x],x,Y[x]};
	for(int L=0,R=0;L<N;L=R){
		int mn=rk_Y[P[L].y],mx=mn;
		for(R=L+1;R<N&&diff(rk_Y[P[R].y],rk_Y[P[R-1].y])==1;R++){
			cmin(mn,rk_Y[P[R].y]);
			cmax(mx,rk_Y[P[R].y]);
		}
		if(R-L>1){
			int l=L,r=R;
			long long dis[2][2]={{0,inf},{inf,0}};
			bool fl=1;
//			printf("L=%d R=%d\n",L,R);
			while(fl){
				fl=0;
				Point*p[2][2]={{P+l,P+r-1},{P+l,P+r-1}};
				int G[2][2]={0},last_mn=mn,last_mx=mx;
				bool dir=l&&P[l-1].y<P[l].y;
				for(;l;fl=1){
					int y=rk_Y[P[l-1].y];
					if(y==mn-1&&dir)--mn;
					else if(y==mx+1&&!dir)++mx;
					else break;
					--l;
					G[0][0]+=dist(p[0][0],P+l);G[0][1]+=dist(p[0][0],P+l)*2;
					G[1][0]+=dist(p[0][1],P+l);G[1][1]+=dist(p[0][1],P+l)*2;
					p[0][0]=p[0][1]=P+l;
//					printf("[%d,%d;%d,%d]\n",G[0][0],G[0][1],G[1][0],G[1][1]);
				}
				if(p[0][0]!=p[0][1])G[1][0]+=dist(p[0][0],p[0][1]);
				dir=r<N&&P[r].y>P[r-1].y;
				mn=last_mn;mx=last_mx;
				for(;r<N;fl=1){
					int y=rk_Y[P[r].y];
					if(y==mn-1&&!dir)--mn;
					else if(y==mx+1&&dir)++mx;
					else break;
					G[0][0]+=dist(p[1][0],P+r)*2;G[0][1]+=dist(p[1][0],P+r);
					G[1][0]+=dist(p[1][1],P+r)*2;G[1][1]+=dist(p[1][1],P+r);
					p[1][0]=p[1][1]=P+r;r++;
//					printf("[%d,%d;%d,%d]\n",G[0][0],G[0][1],G[1][0],G[1][1]);
				}
				if(p[1][0]!=p[1][1])G[0][1]+=dist(p[1][0],p[1][1]);
				cmin(mn,rk_Y[P[l].y]);
				cmax(mx,rk_Y[P[l].y]);
				long long d[2][2]={{inf,inf},{inf,inf}};
				for(int i=0;i<2;i++)
					for(int j=0;j<2;j++)
						for(int k=0;k<2;k++)if(dis[i][j]+G[j][k]<d[i][k])d[i][k]=dis[i][j]+G[j][k];
//				printf("l=%d r=%d\n",l,r);
				for(int i=0;i<2;i++)
					for(int j=0;j<2;j++)dis[i][j]=d[i][j];//,printf("d(%d,%d)=%lld\n",i,j,d[i][j]);
			}
			pre_len[L]=0;
			for(int i=L;i+1<R;i++)pre_len[i+1]=pre_len[i]+dist(P+i,P+i+1);
			for(int i=L;i<R;i++){
				long long d[2]={pre_len[R-1]*2-pre_len[i],pre_len[R-1]+pre_len[i]};
				ans[P[i].i]=inf;
				for(int j=0;j<2;j++)
					for(int k=0;k<2;k++)if(d[j]+dis[j][k]<ans[P[i].i])ans[P[i].i]=d[j]+dis[j][k];
				ans[P[i].i]-=r-l-1;
			}
		}
	}
	for(int i=0;i<N;i++)printf("%lld\n",ans[i]);
}