#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
#define incm(x,y) {x=((x)+(y))%mod;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
struct ii
{
	int x,y,id;
}b[200005];
int n,m,i,j,mx[200005][19],mi[200005][19],a[200005],x,y,smi[800005],tag[800005],lg[800005];
int l[400005],r[400005],id[400005],rstl[400005],typ[400005];
int stk0[400005],stk1[400005],stk2[400005],tp0,tp1,tp2,cnt,rt;
long long dp[400005][2],res[400005];
vector<int> bi[400005];int fa[400005][19],dep[400005];
vector<int> allx,ally;
int qrymin(int l,int r)
{
	int k=lg[r-l+1];
	return min(mi[l][k],mi[r-(1<<k)+1][k]);
}
int qrymax(int l,int r)
{
	int k=lg[r-l+1];
	return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
bool check(int l,int r)
{
	int vl=qrymin(l,r),vr=qrymax(l,r);
	return vr-vl+1==r-l+1;
}
void upd(int x,int y)
{
	tag[x]+=y;
	smi[x]+=y;
}
void pushdo(int x)
{
	if(tag[x]){
		upd(x*2,tag[x]);
		upd(x*2+1,tag[x]);
		tag[x]=0;
	}
}
void update(int x,int l,int r,int ql,int qr,int c)
{
	if(ql<=l&&r<=qr){
		upd(x,c);
		return;
	}int mid=(l+r)/2;
	pushdo(x);
	if(ql<=mid)update(x+x,l,mid,ql,qr,c);
	if(qr>mid)update(x+x+1,mid+1,r,ql,qr,c);
	smi[x]=min(smi[x+x],smi[x+x+1]);
}
int query(int x,int l,int r)
{
	while(l<r){
		pushdo(x);
		int mid=(l+r)/2;
		if(!smi[x+x]){
			x=x+x;r=mid;
		}
		else{
			x=x+x+1;l=mid+1;
		}
	}
	return l;
}
void build()
{
	int i;tp0=tp1=tp2=cnt=0;
	fz1(i,n){
		while(tp1&&a[stk1[tp1]]>=a[i]){
			update(1,1,n,stk1[tp1-1]+1,stk1[tp1],a[stk1[tp1]]);
			tp1--;
		}stk1[++tp1]=i;update(1,1,n,stk1[tp1-1]+1,stk1[tp1],-a[stk1[tp1]]);
		
		while(tp2&&a[stk2[tp2]]<=a[i]){
			update(1,1,n,stk2[tp2-1]+1,stk2[tp2],-a[stk2[tp2]]);
			tp2--;
		}stk2[++tp2]=i;update(1,1,n,stk2[tp2-1]+1,stk2[tp2],a[stk2[tp2]]);
		
		int le=query(1,1,n),cur=id[i]=++cnt;
		l[cur]=r[cur]=i;
		while(tp0&&l[stk0[tp0]]>=le){
			if(typ[stk0[tp0]]&&check(rstl[stk0[tp0]],i)){
				bi[stk0[tp0]].push_back(cur);
				rstl[stk0[tp0]]=l[cur];
				r[stk0[tp0]]=r[cur];
				cur=stk0[tp0--];
			}
			else if(check(l[stk0[tp0]],i)){
				typ[++cnt]=1;
				bi[cnt].push_back(stk0[tp0]);
				bi[cnt].push_back(cur);
				l[cnt]=l[stk0[tp0]];
				rstl[cnt]=l[cur];
				r[cnt]=r[cur];
				--tp0;
				cur=cnt;
			}
			else{
				typ[++cnt]=0;
				bi[cnt].push_back(cur);
				bi[cnt].push_back(stk0[tp0--]);
				while(tp0&&!check(l[stk0[tp0]],i)){
					bi[cnt].push_back(stk0[tp0--]);
				}
				l[cnt]=l[stk0[tp0]];
				r[cnt]=r[cur];
				bi[cnt].push_back(stk0[tp0--]);
				reverse(bi[cnt].begin(),bi[cnt].end());
				cur=cnt;
			}
		}
		stk0[++tp0]=cur;
		update(1,1,n,1,i,-1);
	}
	rt=stk0[1];
}
int dis(int x,int y)
{
	return abs(b[x].x-b[y].x)+abs(b[x].y-b[y].y);
}
void dfs(int x,int p)
{
	int tl=0,tr=0,i;
	fz0k(i,bi[x].size()){
		if(typ[x]){
			tr=max(tr,i);
			if(i&&l[bi[x][i-1]]<r[bi[x][i-1]]) tl=i;
			while(tr+1<bi[x].size()&&l[bi[x][tr+1]]==r[bi[x][tr+1]]) tr++;
		}
		else{
			tl=tr=i;
		}
		int gl=l[bi[x][tl]],gr=r[bi[x][tr]],y=bi[x][i],fl=l[y],fr=r[y];
		if(tl==0&&tr==bi[x].size()-1){
			dp[y][0]=min(dp[x][0]+dis(fl,gr)+dis(gl,gr),dp[x][1]+dis(fl,gl)+dis(gl,gr));
			dp[y][1]=min(dp[x][0]+dis(fr,gr)+dis(gl,gr),dp[x][1]+dis(fr,gl)+dis(gl,gr));
			if(fl==gl) dp[y][1]=min(dp[y][1],dp[x][1]+dis(fr,gr));
			if(fr==gr) dp[y][0]=min(dp[y][0],dp[x][0]+dis(fl,gl)); 
		}
		else{
			dp[y][0]=min(dis(fl,gr)+dis(gl,gr),dis(fl,gl)+dis(gl,gr));
			dp[y][1]=min(dis(fr,gr)+dis(gl,gr),dis(fr,gl)+dis(gl,gr));
			if(fl==gl) dp[y][1]=min(dp[y][1],0ll+dis(fr,gr));
			if(fr==gr) dp[y][0]=min(dp[y][0],0ll+dis(fl,gl));
		}
		dp[y][0]-=(tr-tl);
		dp[y][1]-=(tr-tl);
	}
	ff(bi[x],it){
		dfs(*it,x);
	}
}
bool cmp(ii x,ii y)
{
	return x.x<y.x;
}
int main()
{
	read(n);
	fz1(i,n){
		read(b[i].x);
		read(b[i].y);
		b[i].id=i;
//		allx.push_back(b[i].x);
		ally.push_back(b[i].y);
	}
//	sort(allx.begin(),allx.end());
//	allx.resize(unique(allx.begin(),allx.end())-allx.begin());
	sort(ally.begin(),ally.end());
	ally.resize(unique(ally.begin(),ally.end())-ally.begin());
	sort(b+1,b+n+1,cmp);
	fz1(i,n){
		a[i]=upper_bound(ally.begin(),ally.end(),b[i].y)-ally.begin();
	}
	fz(i,2,200000){
		lg[i]=lg[i/2]+1;
	}
	fz1(i,n){
		mx[i][0]=mi[i][0]=a[i];
	}
	fz1(j,18)fz1(i,n-(1<<j)+1){
		mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
		mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
	}
	build();
	dep[rt]=1;
/*	fz1(i,cnt){
		ff(bi[i],it)cerr<<*it<<' ';cerr<<endl;
	}*/
	dfs(rt,0);
	fz1(i,n){
		res[b[i].id]=min(dp[id[i]][0],dp[id[i]][1]);
	}
	fz1(i,n){
		printf("%lld\n",res[i]);
	}
	return 0;
}
### Prompt

Create a solution in CPP for the following 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

### Response

```cpp
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
#define incm(x,y) {x=((x)+(y))%mod;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
struct ii
{
	int x,y,id;
}b[200005];
int n,m,i,j,mx[200005][19],mi[200005][19],a[200005],x,y,smi[800005],tag[800005],lg[800005];
int l[400005],r[400005],id[400005],rstl[400005],typ[400005];
int stk0[400005],stk1[400005],stk2[400005],tp0,tp1,tp2,cnt,rt;
long long dp[400005][2],res[400005];
vector<int> bi[400005];int fa[400005][19],dep[400005];
vector<int> allx,ally;
int qrymin(int l,int r)
{
	int k=lg[r-l+1];
	return min(mi[l][k],mi[r-(1<<k)+1][k]);
}
int qrymax(int l,int r)
{
	int k=lg[r-l+1];
	return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
bool check(int l,int r)
{
	int vl=qrymin(l,r),vr=qrymax(l,r);
	return vr-vl+1==r-l+1;
}
void upd(int x,int y)
{
	tag[x]+=y;
	smi[x]+=y;
}
void pushdo(int x)
{
	if(tag[x]){
		upd(x*2,tag[x]);
		upd(x*2+1,tag[x]);
		tag[x]=0;
	}
}
void update(int x,int l,int r,int ql,int qr,int c)
{
	if(ql<=l&&r<=qr){
		upd(x,c);
		return;
	}int mid=(l+r)/2;
	pushdo(x);
	if(ql<=mid)update(x+x,l,mid,ql,qr,c);
	if(qr>mid)update(x+x+1,mid+1,r,ql,qr,c);
	smi[x]=min(smi[x+x],smi[x+x+1]);
}
int query(int x,int l,int r)
{
	while(l<r){
		pushdo(x);
		int mid=(l+r)/2;
		if(!smi[x+x]){
			x=x+x;r=mid;
		}
		else{
			x=x+x+1;l=mid+1;
		}
	}
	return l;
}
void build()
{
	int i;tp0=tp1=tp2=cnt=0;
	fz1(i,n){
		while(tp1&&a[stk1[tp1]]>=a[i]){
			update(1,1,n,stk1[tp1-1]+1,stk1[tp1],a[stk1[tp1]]);
			tp1--;
		}stk1[++tp1]=i;update(1,1,n,stk1[tp1-1]+1,stk1[tp1],-a[stk1[tp1]]);
		
		while(tp2&&a[stk2[tp2]]<=a[i]){
			update(1,1,n,stk2[tp2-1]+1,stk2[tp2],-a[stk2[tp2]]);
			tp2--;
		}stk2[++tp2]=i;update(1,1,n,stk2[tp2-1]+1,stk2[tp2],a[stk2[tp2]]);
		
		int le=query(1,1,n),cur=id[i]=++cnt;
		l[cur]=r[cur]=i;
		while(tp0&&l[stk0[tp0]]>=le){
			if(typ[stk0[tp0]]&&check(rstl[stk0[tp0]],i)){
				bi[stk0[tp0]].push_back(cur);
				rstl[stk0[tp0]]=l[cur];
				r[stk0[tp0]]=r[cur];
				cur=stk0[tp0--];
			}
			else if(check(l[stk0[tp0]],i)){
				typ[++cnt]=1;
				bi[cnt].push_back(stk0[tp0]);
				bi[cnt].push_back(cur);
				l[cnt]=l[stk0[tp0]];
				rstl[cnt]=l[cur];
				r[cnt]=r[cur];
				--tp0;
				cur=cnt;
			}
			else{
				typ[++cnt]=0;
				bi[cnt].push_back(cur);
				bi[cnt].push_back(stk0[tp0--]);
				while(tp0&&!check(l[stk0[tp0]],i)){
					bi[cnt].push_back(stk0[tp0--]);
				}
				l[cnt]=l[stk0[tp0]];
				r[cnt]=r[cur];
				bi[cnt].push_back(stk0[tp0--]);
				reverse(bi[cnt].begin(),bi[cnt].end());
				cur=cnt;
			}
		}
		stk0[++tp0]=cur;
		update(1,1,n,1,i,-1);
	}
	rt=stk0[1];
}
int dis(int x,int y)
{
	return abs(b[x].x-b[y].x)+abs(b[x].y-b[y].y);
}
void dfs(int x,int p)
{
	int tl=0,tr=0,i;
	fz0k(i,bi[x].size()){
		if(typ[x]){
			tr=max(tr,i);
			if(i&&l[bi[x][i-1]]<r[bi[x][i-1]]) tl=i;
			while(tr+1<bi[x].size()&&l[bi[x][tr+1]]==r[bi[x][tr+1]]) tr++;
		}
		else{
			tl=tr=i;
		}
		int gl=l[bi[x][tl]],gr=r[bi[x][tr]],y=bi[x][i],fl=l[y],fr=r[y];
		if(tl==0&&tr==bi[x].size()-1){
			dp[y][0]=min(dp[x][0]+dis(fl,gr)+dis(gl,gr),dp[x][1]+dis(fl,gl)+dis(gl,gr));
			dp[y][1]=min(dp[x][0]+dis(fr,gr)+dis(gl,gr),dp[x][1]+dis(fr,gl)+dis(gl,gr));
			if(fl==gl) dp[y][1]=min(dp[y][1],dp[x][1]+dis(fr,gr));
			if(fr==gr) dp[y][0]=min(dp[y][0],dp[x][0]+dis(fl,gl)); 
		}
		else{
			dp[y][0]=min(dis(fl,gr)+dis(gl,gr),dis(fl,gl)+dis(gl,gr));
			dp[y][1]=min(dis(fr,gr)+dis(gl,gr),dis(fr,gl)+dis(gl,gr));
			if(fl==gl) dp[y][1]=min(dp[y][1],0ll+dis(fr,gr));
			if(fr==gr) dp[y][0]=min(dp[y][0],0ll+dis(fl,gl));
		}
		dp[y][0]-=(tr-tl);
		dp[y][1]-=(tr-tl);
	}
	ff(bi[x],it){
		dfs(*it,x);
	}
}
bool cmp(ii x,ii y)
{
	return x.x<y.x;
}
int main()
{
	read(n);
	fz1(i,n){
		read(b[i].x);
		read(b[i].y);
		b[i].id=i;
//		allx.push_back(b[i].x);
		ally.push_back(b[i].y);
	}
//	sort(allx.begin(),allx.end());
//	allx.resize(unique(allx.begin(),allx.end())-allx.begin());
	sort(ally.begin(),ally.end());
	ally.resize(unique(ally.begin(),ally.end())-ally.begin());
	sort(b+1,b+n+1,cmp);
	fz1(i,n){
		a[i]=upper_bound(ally.begin(),ally.end(),b[i].y)-ally.begin();
	}
	fz(i,2,200000){
		lg[i]=lg[i/2]+1;
	}
	fz1(i,n){
		mx[i][0]=mi[i][0]=a[i];
	}
	fz1(j,18)fz1(i,n-(1<<j)+1){
		mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
		mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
	}
	build();
	dep[rt]=1;
/*	fz1(i,cnt){
		ff(bi[i],it)cerr<<*it<<' ';cerr<<endl;
	}*/
	dfs(rt,0);
	fz1(i,n){
		res[b[i].id]=min(dp[id[i]][0],dp[id[i]][1]);
	}
	fz1(i,n){
		printf("%lld\n",res[i]);
	}
	return 0;
}
```