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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
typedef long long ll;
#define N 200020
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
struct Rook{
	int x,y,id;
	bool operator <(const Rook b)const{
		return x<b.x;
	}
}a[N];
int n;
vector<int> ys;
pair<ll,ll> ans[N];

inline int Abs(int x){
	return x>=0?x:-x;
}
inline int Dis(int i,int j){
	return Abs(a[i].x-a[j].x)+Abs(a[i].y-a[j].y);
}

int main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i].id=i;
		a[i].x=read(),a[i].y=read();
		ys.push_back(a[i].y);
	}
	sort(a+1,a+n+1);
	ys.push_back(-inf),ys.push_back(inf);
	sort(ys.begin(),ys.end());
	memset(ans,-1,sizeof(ans));
	for(int S=1;S<=n;++S){
		if(~ans[a[S].id].first)continue;
		int by=lower_bound(ys.begin(),ys.end(),a[S].y)-ys.begin();
		int ly=by-1,ry=by+1,L=S,R=S;
		int las=-1;
		bool ok;
		vector<pair<int,int> > it;
		do{
			ok=false;
			for(int i:{L-1,R+1}){
				if(i<1||i>n)continue;
				bool pre=ys[ly]==a[i].y,suf=ys[ry]==a[i].y;
				if(pre||suf){
					int dir=(pre==(i==L-1));
					if(las^dir){
						if(~las)it.emplace_back(L,R);
						las=dir;
					}
					if(pre)--ly;else ++ry;
					if(i==L-1)--L;else ++R;
					ok=true;break;
				}
			}
		}while(ok);
		if(it.empty()||it.back()!=make_pair(L,R)){
			it.emplace_back(L,R);
		}
		static ll dp[N][2];
		int m=it.size();
		dp[m-1][0]=dp[m-1][1]=0;
		for(int u=m-1;u>=1;--u){
			int L1=it[u].first,R1=it[u].second;
			int L2=it[u-1].first,R2=it[u-1].second;
			dp[u-1][0]=min(dp[u][0]+((R1==R2)?Dis(L1,L2):Dis(L1,R1)+Dis(R1,L2)),dp[u][1]+Dis(R1,L1)+Dis(L1,L2));
			dp[u-1][1]=min(dp[u][1]+((L1==L2)?Dis(R1,R2):Dis(R1,L1)+Dis(L1,R2)),dp[u][0]+Dis(L1,R1)+Dis(R1,R2));
		}
		int eL=it[0].first,eR=it[0].second;
		for(int i=eL;i<=eR;++i){
			ans[a[i].id]=make_pair(R-L,min(dp[0][0]+Dis(eL,eR)+Dis(eR,i),dp[0][1]+Dis(eR,eL)+Dis(eL,i)));
		}
	}
	for(int i=1;i<=n;++i){
		printf("%lld\n",ans[i].second-ans[i].first);
	}
	return 0;
}