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;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
inline int read()
{
    int s=0,f=1; char ch=getchar();
    while(!isdigit(ch) && ch!='-')ch=getchar();
    if(ch=='-')ch=getchar(),f=-1;
    while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
    return ~f?s:-s;
}

const int maxn=2e5+20;
const ll inf=0x3f3f3f3f3f3f3f3f;

struct point {
    int x,y,id;
};
point p[maxn];
int ny[maxn],idy[maxn];
int to[maxn];

int n;

int l[maxn],r[maxn];

int sx[maxn];
int fa[maxn];
vector<int>ed[maxn]; int rd[maxn];

ll dp[maxn][2][2];

int rk[maxn],tp;
ll ans[maxn];

inline void get_rk()
{
    queue<int>q;
    REP(i,1,n)if(fa[i]==i && !rd[i])q.push(i);
    while(!q.empty())
    {
	int u=q.front();q.pop();
	rk[++tp]=u;
	for(int v:ed[u])
	    if(!(--rd[v]))
		q.push(v);
    }
}

inline void init()
{
    n=read();
    REP(i,1,n)p[i]=(point){read(),read(),i};
    sort(p+1,p+n+1,[](point a,point b){ return a.x<b.x;});
    REP(i,1,n)sx[i]=p[i].y; sort(sx+1,sx+n+1);
    REP(i,1,n)ny[i]=lower_bound(sx+1,sx+n+1,p[i].y)-sx,idy[ny[i]]=i;
    REP(i,1,n)fa[i]=i,l[i]=i,r[i]=i;
    REP(i,1,n)to[p[i].id]=i;
    REP(i,1,n-1)
    {
	if(abs(ny[i]-ny[i+1])==1)fa[i+1]=fa[i],r[fa[i+1]]=i+1;
	else {
	    int x=ny[i]+(ny[i]<ny[i+1]?1:-1);
	    if(idy[x]<i) ed[i+1].push_back(fa[i]),rd[fa[i]]++;
	    else ed[fa[i]].push_back(i+1),rd[i+1]++;
	}
    }
    DREP(i,n,1)l[i]=l[fa[i]],r[i]=r[fa[i]];
    get_rk();
}

inline int Dis(int i,int j){ return abs(p[j].x-p[i].x)+abs(p[j].y-p[i].y);}

inline void doing()
{
    REP(th,1,tp)
    {
	int u=rk[th];

	if(u==1)
	    u=1;
	
	int reml=l[u],remr=r[u];
	int &lx=l[u],&rx=r[u];
	
	dp[u][0][1]=l[u]==r[u]?0:Dis(l[u],r[u]);
	dp[u][1][0]=l[u]==r[u]?0:Dis(r[u],l[u]);
	dp[u][0][0]=dp[u][1][1]=inf;
	
	int L,R,ly,ry;
	ly=min(ny[lx],ny[rx]),ry=max(ny[lx],ny[rx]);
	
	do{
	    
	    int le=lx>1 && (ly-1==ny[lx-1] || ny[lx-1]==ry+1),re=rx<n && (ly-1==ny[rx+1] || ry+1==ny[rx+1]);
	    L=fa[lx-1],R=rx+1;
	    if(!le && !re)break;
	    if(le && re)
	    {
		static ll f[2][2]; memset(f,inf,sizeof(f));
		REP(st,0,1)REP(now,0,1)
		{
		    chkmin(f[st][0],dp[u][st][now]+Dis(now?rx:lx,rx+1)+dp[R][0][1]+Dis(r[rx+1],lx-1)+dp[L][1][0]);
		    chkmin(f[st][1],dp[u][st][now]+Dis(now?rx:lx,lx-1)+dp[L][1][0]+Dis(l[lx-1],rx+1)+dp[R][0][1]);
		}
		memcpy(dp[u],f,sizeof(f));
		chkmax(ry,max(ny[rx+1],ny[r[rx+1]]));
		chkmin(ly,min(ny[rx+1],ny[r[rx+1]]));
		chkmax(ry,max(ny[lx-1],ny[l[lx-1]]));
		chkmin(ly,min(ny[lx-1],ny[l[lx-1]]));
		lx=l[lx-1]; rx=r[rx+1];
		
	    }
	    else if(le)
	    {
		static ll f[2][2]; memset(f,inf,sizeof(f));
		REP(st,0,1)REP(now,0,1)
		{
		    chkmin(f[st][0],dp[u][st][now]+Dis(now?rx:lx,lx-1)+dp[L][1][0]);
		}
		memcpy(dp[u],f,sizeof(f));
		chkmax(ry,max(ny[lx-1],ny[l[lx-1]]));
		chkmin(ly,min(ny[lx-1],ny[l[lx-1]]));
		lx=l[lx-1];
	    }else
	    {
		static ll f[2][2]; memset(f,inf,sizeof(f));
		REP(st,0,1)REP(now,0,1)
		{
		    chkmin(f[st][1],dp[u][st][now]+Dis(now?rx:lx,rx+1)+dp[R][0][1]);
		}
		memcpy(dp[u],f,sizeof(f));
		chkmax(ry,max(ny[rx+1],ny[r[rx+1]]));
		chkmin(ly,min(ny[rx+1],ny[r[rx+1]]));
		rx=r[rx+1];
	    
	    }
	}while(1);
	REP(j,reml,remr)
	{
	    if(j==reml)ans[p[j].id]=min(dp[u][0][0],dp[u][0][1]);
	    else if(j==remr)ans[p[j].id]=min(dp[u][1][0],dp[u][1][1]);
	    else {
		ans[p[j].id]=inf;
		REP(op,0,1)chkmin(ans[p[j].id],min(dp[u][0][op]+Dis(j,reml),dp[u][1][op]+Dis(j,remr)));
	    }
	    ans[p[j].id]-=rx-lx;
	}
    }
    REP(i,1,n)printf("%lld\n",ans[i]);
}

int main()
{

    init();
    doing();
    return 0;
}