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;

struct Node {
	int pl,pr,vl,vr,type;
	vector<int> sons;
} a[404040];

struct Point {
	int x,y,tag;
}point[202020];

int n,tot,x[202020],y[202020],p[202020],rkx[202020],rky[202020];
long long ans[202020],dp[404040][2];
inline int dist(int a, int b) {
	return abs(x[p[a]]-x[p[b]])+abs(y[p[a]]-y[p[b]]);
}

int l[202020],r[202020];

void work(int pos) {
	//cout << pos << endl;
	if (pos <= n) {
		ans[p[pos]] = dp[pos][0];
		return;
	}
	vector <int> &s = a[pos].sons;
	for (int i = 0, last = a[pos].pl;i < s.size(); i++) {
		l[i] = last; if (a[s[i]].type != 0) last = a[s[i]].pr + 1;
	}
	for (int i = s.size() - 1, last = a[pos].pr; i >= 0; i--) {
		r[i] = last; if (a[s[i]].type != 0) last = a[s[i]].pl - 1;
	}
	for (int i = 0;i < s.size(); i++) {
		int dest = s[i], pl = l[i], pr = r[i];
		
		if (pl == a[dest].pl && pr == a[dest].pr) 
			dp[dest][0] = dp[dest][1] = 0;
		
		else if (pl == a[dest].pl) {
			if (pl == a[pos].pl && pr == a[pos].pr) {
				dp[dest][0] = dist(a[dest].pl, pr) + dp[pos][1];
				dp[dest][1] = dist(a[dest].pr, pr) + dp[pos][1];
			}
			else {
				dp[dest][0] = dist(a[dest].pl, pr);
				dp[dest][1] = dist(a[dest].pr, pr);
			}
		} else if (pr == a[dest].pr) {
			if (pl == a[pos].pl && pr == a[pos].pr) {
				dp[dest][0] = dist(a[dest].pl, pl) + dp[pos][0];
				dp[dest][1] = dist(a[dest].pr, pl) + dp[pos][0];
			}
			else {
				dp[dest][0] = dist(a[dest].pl, pl);
				dp[dest][1] = dist(a[dest].pr, pl);
			}
		} else {
			if (pl == a[pos].pl && pr == a[pos].pr) {
				dp[dest][0] = min(dp[pos][0] + dist(a[dest].pl, pr) + dist(pl, pr), dp[pos][1] + dist(a[dest].pl, pl) + dist(pl, pr));
				dp[dest][1] = min(dp[pos][0] + dist(a[dest].pr, pr) + dist(pl, pr), dp[pos][1] + dist(a[dest].pr, pl) + dist(pl, pr));
			} else {
				dp[dest][0] = min(dist(a[dest].pl, pr) + dist(pl, pr), dist(a[dest].pl, pl) + dist(pl, pr));
				dp[dest][1] = min(dist(a[dest].pr, pr) + dist(pl, pr), dist(a[dest].pr, pl) + dist(pl, pr));
			}
		}
		dp[dest][0] -= a[dest].pl - pl + pr - a[dest].pr;
		dp[dest][1] -= a[dest].pl - pl + pr - a[dest].pr;
	}
	for (int i = 0;i < s.size(); i++)
		work(s[i]);
}
inline bool chk(Node &A,Node &B) {
	return max(A.vr,B.vr)-min(A.vl,B.vl) == max(A.pr,B.pr)-min(A.pl,B.pl);
}
inline int join(int x, int y) {
	if (a[x].vl < a[y].vl) {
		a[++tot].type = 1;
		a[tot].pl = a[x].pl;
		a[tot].vl = a[x].vl;
		a[tot].pr = a[y].pr;
		a[tot].vr = a[y].vr;
	} 
	else {		
		a[++tot].type = -1;
		a[tot].pl = a[x].pl;
		a[tot].vl = a[y].vl;
		a[tot].pr = a[y].pr;
		a[tot].vr = a[x].vr;
	}
	a[tot].sons.push_back(x);
	a[tot].sons.push_back(y);
	return tot;
}
int s[202020];
inline void buildTree() {
	for (int i = 1;i <= n; i++) {
		a[++tot].type = 0;
		a[tot].pl = a[tot].pr = i;
		a[tot].vl = a[tot].vr = rky[p[i]];
	}
	int top = 0;
	for (int i = 1;i <= n; i++) {
		bool fl = 1;
		s[++top] = i;
		while (fl) {
			fl = 0;
			if (top >= 2 && a[s[top - 1]].type == 1 && a[s[top - 1]].vr + 1 == a[s[top]].vl) {
				a[s[top - 1]].vr = a[s[top]].vr;
				a[s[top - 1]].pr = a[s[top]].pr;
				a[s[top - 1]].sons.push_back(s[top]);
				fl = 1;
				top--;
			} 
			else if (top >= 2 && a[s[top - 1]].type == -1 && a[s[top - 1]].vl - 1 == a[s[top]].vr) {
				a[s[top - 1]].vl = a[s[top]].vl;
				a[s[top - 1]].pr = a[s[top]].pr;
				a[s[top - 1]].sons.push_back(s[top]);
				fl = 1;
				top--;
			} 
			else if (top >= 2 && chk(a[s[top]],a[s[top-1]])) {
				int x,y;
				y = s[top--];
				x = s[top--];
				s[++top] = join(x, y);
				fl = 1;
			}
		}
	}
	for (int i = 1;i <= top; i++)
		work(s[i]);
}
bool cmpx(Point A,Point B) {
	return A.x < B.x;
}
bool cmpy(Point A,Point B) {
	return A.y < B.y;
}
int main() {
	scanf("%d",&n); 
	for (int i = 1;i <= n; i++) {
		scanf("%d%d",&point[i].x,&point[i].y),point[i].tag = i;
		x[i] = point[i].x;
		y[i] = point[i].y;
	}
	sort(point+1,point+n+1,cmpx);
	for (int i = 1;i <= n; i++)
		rkx[point[i].tag] = i;
		
	sort(point+1,point+n+1,cmpy);
	for (int i = 1;i <= n; i++)
		rky[point[i].tag] = i;
		
	for (int i = 1;i <= n; i++)
		p[rkx[i]] = i;
		
	buildTree();
	
	for (int i = 1; i <= n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}