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;
const int maxn=200009;

int n;
struct Point{
	int x,y,id;
	bool operator < (const Point &rhs) const{
		return x<rhs.x;
	}
}r[maxn];

int sy[maxn];

long long ans[maxn];
long long f[maxn][2];
vector<pair<int,int>>section;

int dist(int i,int j){
	return abs(r[i].x-r[j].x)+abs(r[i].y-r[j].y);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		r[i].id=i;scanf("%d%d",&r[i].x,&r[i].y);
		sy[i]=r[i].y;
	}
	sort(r+1,r+1+n);
	sort(sy+1,sy+1+n);sy[0]=0;sy[n+1]=1e9;
	
	for(int i=1;i<=n;++i)ans[i]=-1;
	for(int i=1;i<=n;++i){
		if(ans[r[i].id]!=-1)continue;
		int t=lower_bound(sy+1,sy+1+n,r[i].y)-sy;
		int t1=t-1,t2=t+1,L=i,R=i,predir=-1,dir;
		for(;;){
			int flag=0; 
			for(int i:{L-1,R+1}){
				if(i<=0||i>n)continue;
				if(r[i].y!=sy[t1]&&r[i].y!=sy[t2])continue;
				if(i==L-1){
					dir=r[i].y==sy[t1];
				}else{
					dir=r[i].y==sy[t2];
				}
				if(predir!=-1&&dir!=predir){
					section.push_back(pair<int,int>(L,R));
				}
				predir=dir;
				if(r[i].y==sy[t1])--t1;else ++t2;
				if(i==L-1)--L;else ++R;
				flag=1;
			}
			if(!flag)break;
		}
		section.push_back(pair<int,int>(L,R));
		
		int s=section.size();
		f[s-1][0]=f[s-1][1]=0;
		for(int i=s-1;i>=1;--i){
			int l1=section[i].first,r1=section[i].second;
			int l2=section[i-1].first,r2=section[i-1].second;
			f[i-1][0]=min(dist(l2,l1)+dist(l1,r1)+f[i][1],(r1==r2?dist(l1,l2):dist(l2,r1)+dist(r1,l1))+f[i][0]);
			f[i-1][1]=min(dist(r2,r1)+dist(r1,l1)+f[i][0],(l1==l2?dist(r1,r2):dist(r2,l1)+dist(l1,r1))+f[i][1]);
		}
		L=section[0].first;R=section[0].second;
		for(int i=L;i<=R;++i){
			int id=r[i].id;
			ans[id]=min(dist(i,R)+dist(R,L)+f[0][0],dist(i,L)+dist(L,R)+f[0][1])-(section[s-1].second-section[s-1].first);
		}
		section.clear();
	}
	
	for(int i=1;i<=n;++i)printf("%lld\n",ans[i]);
	
	return 0;
}