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 ox[N+9],oy[N+9];

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

int id[N+9],p[N+9];

void Get_id(){
  sort(ox+1,ox+n+1);
  sort(oy+1,oy+n+1);
  for (int i=1;i<=n;++i){
	x[i]=lower_bound(ox+1,ox+n+1,x[i])-ox;
	y[i]=lower_bound(oy+1,oy+n+1,y[i])-oy;
	id[x[i]]=i;p[x[i]]=y[i];
  }
}

int le[N+9],ri[N+9];

void Get_le_ri(){
  le[1]=1;ri[n]=n;
  for (int i=2;i<=n;++i) le[i]=abs(p[i]-p[i-1])==1?le[i-1]:i;
  for (int i=n-1;i>=1;--i) ri[i]=abs(p[i]-p[i+1])==1?ri[i+1]:i;
}

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

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

LL Dfs_dp(int l,int r,int t,int mn,int mx){
  if (dp[t][l].find(r)!=dp[t][l].end()) return dp[t][l][r];
  LL res=l-r;
  int flag=0;
  if (l>1&&(p[l-1]==mn-1||p[l-1]==mx+1))
	res=Dfs_dp(le[l-1],r,0,min(mn,p[le[l-1]]),max(mx,p[le[l-1]]))+Get_dis(le[l-1],t?r:l),flag=1;
  if (r<n&&(p[r+1]==mn-1||p[r+1]==mx+1)){
	LL now=Dfs_dp(l,ri[r+1],1,min(mn,p[ri[r+1]]),max(mx,p[ri[r+1]]))+Get_dis(ri[r+1],t?r:l);
	res=flag?min(res,now):now;
  }
  return dp[t][l][r]=res;
}

LL ans[N+9];

void Get_dp(){
  for (int i=1;i<=n;++i) ans[id[i]]=Dfs_dp(i,i,0,p[i],p[i]);
}

void work(){
  Get_id();
  Get_le_ri();
  Get_dp();
}

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

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