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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N=2e5+5;
const long long inf=1e18;
pair< pair<int,int> , int > a[N];
int n,x[N],y[N],l[N],r[N];
map<int,long long> f[2][N];
long long dis(pair<int,int> i,pair<int,int> j){
	return abs(x[i.fi]-x[j.fi])+abs(y[i.se]-y[j.se]);
}
long long dfs(int mn,int mx,int l,int r,int k){
	if(f[k][l].count(r)) return f[k][l][r];
	int L=::l[l-1],R=::r[r+1];long long ans=inf;
	if(l>1 && (a[l-1].fi.se==mn-1 || a[l-1].fi.se==mx+1))
		ans=min(ans,dfs(min(a[L].fi.se,mn),max(a[L].fi.se,mx),L,r,0)+dis(a[L].fi,k==0?a[l].fi:a[r].fi));
	if(r<n && (a[r+1].fi.se==mn-1 || a[r+1].fi.se==mx+1))
		ans=min(ans,dfs(min(a[R].fi.se,mn),max(a[R].fi.se,mx),l,R,1)+dis(a[R].fi,k==0?a[l].fi:a[r].fi));
	f[k][l][r]=(ans==inf?l-r:ans);
	return f[k][l][r];
}
long long ans[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>x[i]>>y[i],a[i]=make_pair(make_pair(x[i],y[i]),i);
	sort(a+1,a+n+1);
	sort(x+1,x+n+1);
	sort(y+1,y+n+1);
	for(int i=1;i<=n;++i)
		a[i].fi.fi=lower_bound(x+1,x+n+1,a[i].fi.fi)-x,
		a[i].fi.se=lower_bound(y+1,y+n+1,a[i].fi.se)-y;
	l[1]=1;
	for(int i=2;i<=n;++i)
		if(abs(a[i-1].fi.se-a[i].fi.se)==1) l[i]=l[i-1];
		else l[i]=i;
	r[n]=n;
	for(int i=n-1;i>=1;--i)
		if(abs(a[i+1].fi.se-a[i].fi.se)==1) r[i]=r[i+1];
		else r[i]=i;
	//for(int i=1;i<=n;++i)cout<<a[i].fi.fi<<" "<<a[i].fi.se<<endl;
	for(int i=1;i<=n;++i)
		ans[a[i].se]=dfs(a[i].fi.se,a[i].fi.se,i,i,0);
	for(int i=1;i<=n;++i)
		cout<<ans[i]<<endl;
	return 0;
}