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;
const int MAXN = 2e5 + 5;
const int MAXM = 1e6 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
struct Node {
	int pl, pr, vl, vr, type;
	vector <int> sons;
} a[MAXN * 2];
ll ans[MAXN], dp[MAXN * 2][2];
int n, tot, x[MAXN], y[MAXN], p[MAXN], rkx[MAXN], rky[MAXN];
int dist(int a, int b) {
	if (a == b) return 0;
	else return abs(x[p[a]] - x[p[b]]) + abs(y[p[a]] - y[p[b]]);
}
void work(int pos) {
	if (pos <= n) {
		ans[p[pos]] = dp[pos][0];
		return;
	}
	vector <int> &s = a[pos].sons;
	static int l[MAXN], r[MAXN];
	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]);
}
int leaf(int x) {
	a[++tot].type = 0;
	a[tot].pl = a[tot].pr = x;
	a[tot].vl = a[tot].vr = rky[p[x]];
	return tot;
}
int join(int x, int y) {
	if (a[x].vl < a[y].vl) {
		assert(a[x].vr + 1 == 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 {
		assert(a[y].vr + 1 == a[x].vl);
		a[++tot].type = -1;
		a[tot].pl = a[x].pl, a[tot].vr = a[x].vr;
		a[tot].pr = a[y].pr, a[tot].vl = a[y].vl;
	}
	a[tot].sons.push_back(x);
	a[tot].sons.push_back(y);
	return tot;
}
void buildTree() {
	for (int i = 1; i <= n; i++)
		leaf(i);
	static int s[MAXN]; int top = 0;
	for (int i = 1; i <= n; i++) {
		bool flg = true; s[++top] = i;
		while (flg) {
			flg = false;
			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]);
				flg = true, 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]);
				flg = true, top--;
			} else if (top >= 2 && max(a[s[top]].vr, a[s[top - 1]].vr) - min(a[s[top]].vl, a[s[top - 1]].vl) == max(a[s[top]].pr, a[s[top - 1]].pr) - min(a[s[top]].pl, a[s[top - 1]].pl)) {
				int y = s[top--], x = s[top--];
				s[++top] = join(x, y);
				flg = true;
			}
		}
	}
	for (int i = 1; i <= top; i++)
		work(s[i]);
}
void getrk(int n, int *x, int *rkx) {
	static int cnt[MAXM];
	memset(cnt, 0, sizeof(cnt));
	for (int i = 1; i <= n; i++)
		cnt[x[i]]++;
	for (int i = 1; i < MAXM; i++)
		cnt[i] += cnt[i - 1];
	for (int i = 1; i <= n; i++)
		rkx[i] = cnt[x[i]];
}
int main() {
	read(n);
	for (int i = 1; i <= n; i++)
		read(x[i]), read(y[i]);
	getrk(n, x, rkx);
	getrk(n, y, rky);
	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;
}