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;

typedef long long LL;

const int N=200000;

int n,x[N+9],y[N+9];
int idx[N+9],idy[N+9];

bool cmp0(const int &a,const int &b){return x[a]<x[b];}
bool cmp1(const int &a,const int &b){return y[a]<y[b];}

void into(){
  scanf("%d",&n);
  for (int i=1;i<=n;++i){
	scanf("%d%d",&x[i],&y[i]);
	idx[i]=i;idy[i]=i;
  }
}

int p[N+9],q[N+9];
// p[i] -> 将点离散化后 x=i , y=p[i]

void Get_p(){
  sort(idx+1,idx+n+1,cmp0);
  sort(idy+1,idy+n+1,cmp1);
  for (int i=1;i<=n;++i) q[idy[i]]=i;
  for (int i=1;i<=n;++i) p[i]=q[idx[i]];
}

int bam[N+9],dan[N+9];

// bam[i] -> i 所属连续段的开头
// dan[i] -> i 所属连续短的结尾

void Get_bam(){
  bam[1]=1;dan[n]=n;
  for (int i=2;i<=n;++i) bam[i]=abs(p[i]-p[i-1])==1?bam[i-1]:i;
  for (int i=n-1;i>=1;--i) dan[i]=abs(p[i]-p[i+1])==1?dan[i+1]:i;
}

int Get_dis(int a,int b){
  a=idx[a];b=idx[b];
  return abs(x[a]-x[b])+abs(y[a]-y[b]);
}

map<int,LL>dp[2][N+9];

LL Dfs_ans(int l,int r,bool gg,int mn,int mx){
  map<int,LL>::iterator it=dp[gg][l].find(r);
  if (it!=dp[gg][l].end()) return it->second;
  vector<LL>opt;
  if (l>1&&(p[l-1]==mn-1||p[l-1]==mx+1)){
	LL tmp=Dfs_ans(bam[l-1],r,0,min(mn,p[bam[l-1]]),max(mx,p[bam[l-1]]));
	tmp+=Get_dis(bam[l-1],gg?r:l);
	opt.push_back(tmp);
  }
  if (r<n&&(p[r+1]==mn-1||p[r+1]==mx+1)){
	LL tmp=Dfs_ans(l,dan[r+1],1,min(mn,p[dan[r+1]]),max(mx,p[dan[r+1]]));
	tmp+=Get_dis(gg?r:l,dan[r+1]);
	opt.push_back(tmp);
  }
  LL res=l-r;
  if (opt.size()>=1){
	res=opt.front();
	if (opt.size()>=2) res=min(res,opt[1]);
  }
  return dp[gg][l][r]=res;
}

LL ans[N+9];

void Get_ans(){
  for (int i=1;i<=n;++i) ans[idx[i]]=Dfs_ans(i,i,0,p[i],p[i]);
}

void work(){
  Get_p();
  Get_bam();
  Get_ans();
}

void outo(){
  for (int i=1;i<=n;++i)
	printf("%lld\n",ans[i]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}