#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXN = 200000;
const int MAXNODE = MAXN + MAXN - 1;
struct P { int x, y; };
struct Node { deque<int> lst; vector<int> vec; int kind; int lidx, ridx; };

int n;
P p[MAXN];
ll ans[MAXN];

int x2idx[MAXN];
int xx[MAXN], nxx;
int yy[MAXN], nyy;

int lx[MAXN], hx[MAXN], ly[MAXN], hy[MAXN];
int par[MAXN], sz[MAXN], leader[MAXN];

Node node[MAXNODE]; int nnode;
bool contained[MAXNODE];

ll outsidecost[MAXNODE][2];

int leftmost[MAXNODE], rightmost[MAXNODE]; 
ll totalcostleft[MAXNODE][2], totalcostright[MAXNODE][2];



int dist(int a, int b) { if (a == b) return 0; return abs(xx[p[a].x] - xx[p[b].x]) + abs(yy[p[a].y] - yy[p[b].y]) - 1; }

void dfsinit(int at) {
	vector<int> cur = node[at].vec;
	int len = SZ(cur);
	if (at < n) { assert(len == 0); node[at].lidx = node[at].ridx = x2idx[at]; return; }
	assert(len >= 2);
	REP(i, len) {
		int to = cur[i];
		dfsinit(to);
		if (i == 0) node[at].lidx = node[to].lidx;
		if (i == len - 1) node[at].ridx = node[to].ridx;
	}
}
void dfscalc(int at) {
	vector<int> cur = node[at].vec;
	int len = SZ(cur);
	if (len == 0) return;
	//printf("dfs(%d) (%lld/%lld)\n", at, outsidecost[at][0], outsidecost[at][1]);
	REP(i, len) {
		int to = cur[i];
		if (i - 1 < 0) { leftmost[i] = i, totalcostleft[i][0] = 0, totalcostleft[i][1] = 0; continue; }
		int pto = cur[i - 1];
		if (node[pto].kind != 0) { leftmost[i] = i, totalcostleft[i][0] = 0, totalcostleft[i][1] = 0; continue; }
		leftmost[i] = leftmost[i - 1]; REP(side, 2) totalcostleft[i][side] = dist(side == 0 ? node[to].lidx : node[to].ridx, node[pto].ridx) + totalcostleft[i - 1][1];
	}
	for (int i = len - 1; i >= 0; --i) {
		int to = cur[i];
		if (i + 1 >= len) { rightmost[i] = i, totalcostright[i][0] = 0, totalcostright[i][1] = 0; continue; }
		int pto = cur[i + 1];
		if (node[pto].kind != 0) { rightmost[i] = i, totalcostright[i][0] = 0, totalcostright[i][1] = 0; continue; }
		rightmost[i] = rightmost[i + 1]; REP(side, 2) totalcostright[i][side] = dist(side == 0 ? node[to].lidx : node[to].ridx, node[pto].lidx) + totalcostright[i + 1][0];
	}
	//REP(i, len) printf("%d: leftmost=%d rightmost=%d totalcostleft=%lld/%lld totalcostright=%lld/%lld\n", i, leftmost[i], rightmost[i], totalcostleft[i][0], totalcostleft[i][1], totalcostright[i][0], totalcostright[i][1]);
	REP(i, len) {
		int to = cur[i]; bool canall = leftmost[i] == 0 && rightmost[i] == len - 1;
		REP(side,2) {
			int aidx = i == rightmost[i] ? side == 0 ? node[cur[i]].lidx : node[cur[i]].ridx : node[cur[rightmost[i]]].ridx;
			int bidx = i == leftmost[i] ? side == 0 ? node[cur[i]].lidx : node[cur[i]].ridx : node[cur[leftmost[i]]].lidx;
			ll a = totalcostright[i][side] + (i == leftmost[i] ? 0 : dist(aidx, node[cur[i - 1]].ridx) + totalcostleft[i - 1][1]) + (canall ? outsidecost[at][i != leftmost[i] ? 0 : 1] : 0);
			ll b = totalcostleft[i][side] + (i == rightmost[i] ? 0 : dist(bidx, node[cur[i + 1]].lidx) + totalcostright[i + 1][0]) + (canall ? outsidecost[at][i != rightmost[i] ? 1 : 0] : 0);
			//printf("\t%lld vs %lld\n", a, b);
			outsidecost[to][side] = min(a, b);
		}
	}
	REP(i, len) {
		int to = cur[i];
		dfscalc(to);
	}
}

int makenode(int a, int b, int kind) {
	int ret = nnode++;
	node[ret].lst.clear(); node[ret].lst.PB(a); node[ret].lst.PB(b); node[ret].kind = kind;
	return ret;
}

int merge(int a, int b, int kind) {
	if (node[a].kind == kind && node[b].kind == kind) {
		if (SZ(node[a].lst) >= SZ(node[b].lst)) {
			while (SZ(node[b].lst) != 0) { int x = node[b].lst.front(); node[b].lst.pop_front(); node[a].lst.push_back(x); }
			return a;
		} else {
			while (SZ(node[a].lst) != 0) { int x = node[a].lst.back(); node[a].lst.pop_back(); node[b].lst.push_front(x); }
			return b;
		}
	}
	if (node[a].kind == kind) {
		node[a].lst.push_back(b);
		return a;
	}
	if (node[b].kind == kind) {
		node[b].lst.push_front(a);
		return b;
	}
	return makenode(a, b, kind);
}

int uffind(int x) {
	if (par[x] == x) return par[x];
	return par[x] = uffind(par[x]);
}
void ufunite(int a, int b, int kind) {
	//printf("uniting %d and %d\n", a, b);
	a = uffind(a);
	b = uffind(b);
	int oa = a, ob = b;
	assert(a != b);
	if (sz[a] < sz[b]) swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
	lx[a] = min(lx[a], lx[b]);
	hx[a] = max(hx[a], hx[b]);
	ly[a] = min(ly[a], ly[b]);
	hy[a] = max(hy[a], hy[b]);
	leader[a] = merge(leader[oa], leader[ob], kind);
}

void solve() {
	nxx = 0; REP(i, n) xx[nxx++] = p[i].x; sort(xx, xx + nxx); nxx = unique(xx, xx + nxx) - xx; assert(nxx == n); REP(i, n) p[i].x = lower_bound(xx, xx + nxx, p[i].x) - xx;
	nyy = 0; REP(i, n) yy[nyy++] = p[i].y; sort(yy, yy + nyy); nyy = unique(yy, yy + nyy) - yy; assert(nyy == n); REP(i, n) p[i].y = lower_bound(yy, yy + nyy, p[i].y) - yy;

	nnode = n;
	REP(i, n) {
		int x = p[i].x, y = p[i].y;
		x2idx[x] = i;
		node[x].lst.clear(); node[x].kind = 0;
		par[x] = x, sz[x] = 1, lx[x] = hx[x] = x, ly[x] = hy[x] = y, leader[x] = x;
	}
	REP(i, n) {
		int b = uffind(i);
		while (true) {
			b = uffind(b);
			if (lx[b] - 1 >= 0) {
				int a = uffind(lx[b] - 1);
				assert(hx[a] == lx[b] - 1);
				if (hy[a] == ly[b] - 1) {
					ufunite(a, b, +1);
					continue;
				} else if (ly[a] == hy[b] + 1) {
					ufunite(a, b, -1);
					continue;
				}
			}
			if (hx[b] + 1 < n) {
				int c = uffind(hx[b] + 1);
				assert(lx[c] == hx[b] + 1);
				if (hy[c] == ly[b] - 1) {
					ufunite(b, c, -1);
					continue;
				} else if(ly[c]==hy[b]+1) {
					ufunite(b, c, +1);
					continue;
				}
			}
			break;
		}
	}
	REP(i, nnode) { node[i].vec.clear(); while (SZ(node[i].lst) > 0) { int x = node[i].lst.front(); node[i].lst.pop_front(); node[i].vec.PB(x); } }
	REP(i, nnode) contained[i] = false;
	REP(i, nnode) REPSZ(j, node[i].vec) { int x = node[i].vec[j]; contained[x] = true; }
	//FOR(i, n, nnode) { printf("%d:", i); REPSZ(j, node[i].vec) printf(" %d", node[i].vec[j]); puts(""); }
	REP(i, nnode) if (!contained[i]) { outsidecost[i][0] = outsidecost[i][1] = 0; dfsinit(i); dfscalc(i); }
	REP(i, n) ans[x2idx[i]] = outsidecost[i][0];
}


void run() {
	scanf("%d", &n);
	REP(i, n) scanf("%d%d", &p[i].x, &p[i].y);
	solve();
	REP(i, n) printf("%lld\n", ans[i]);
}

int main() {
	run();
	return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXN = 200000;
const int MAXNODE = MAXN + MAXN - 1;
struct P { int x, y; };
struct Node { deque<int> lst; vector<int> vec; int kind; int lidx, ridx; };

int n;
P p[MAXN];
ll ans[MAXN];

int x2idx[MAXN];
int xx[MAXN], nxx;
int yy[MAXN], nyy;

int lx[MAXN], hx[MAXN], ly[MAXN], hy[MAXN];
int par[MAXN], sz[MAXN], leader[MAXN];

Node node[MAXNODE]; int nnode;
bool contained[MAXNODE];

ll outsidecost[MAXNODE][2];

int leftmost[MAXNODE], rightmost[MAXNODE]; 
ll totalcostleft[MAXNODE][2], totalcostright[MAXNODE][2];



int dist(int a, int b) { if (a == b) return 0; return abs(xx[p[a].x] - xx[p[b].x]) + abs(yy[p[a].y] - yy[p[b].y]) - 1; }

void dfsinit(int at) {
	vector<int> cur = node[at].vec;
	int len = SZ(cur);
	if (at < n) { assert(len == 0); node[at].lidx = node[at].ridx = x2idx[at]; return; }
	assert(len >= 2);
	REP(i, len) {
		int to = cur[i];
		dfsinit(to);
		if (i == 0) node[at].lidx = node[to].lidx;
		if (i == len - 1) node[at].ridx = node[to].ridx;
	}
}
void dfscalc(int at) {
	vector<int> cur = node[at].vec;
	int len = SZ(cur);
	if (len == 0) return;
	//printf("dfs(%d) (%lld/%lld)\n", at, outsidecost[at][0], outsidecost[at][1]);
	REP(i, len) {
		int to = cur[i];
		if (i - 1 < 0) { leftmost[i] = i, totalcostleft[i][0] = 0, totalcostleft[i][1] = 0; continue; }
		int pto = cur[i - 1];
		if (node[pto].kind != 0) { leftmost[i] = i, totalcostleft[i][0] = 0, totalcostleft[i][1] = 0; continue; }
		leftmost[i] = leftmost[i - 1]; REP(side, 2) totalcostleft[i][side] = dist(side == 0 ? node[to].lidx : node[to].ridx, node[pto].ridx) + totalcostleft[i - 1][1];
	}
	for (int i = len - 1; i >= 0; --i) {
		int to = cur[i];
		if (i + 1 >= len) { rightmost[i] = i, totalcostright[i][0] = 0, totalcostright[i][1] = 0; continue; }
		int pto = cur[i + 1];
		if (node[pto].kind != 0) { rightmost[i] = i, totalcostright[i][0] = 0, totalcostright[i][1] = 0; continue; }
		rightmost[i] = rightmost[i + 1]; REP(side, 2) totalcostright[i][side] = dist(side == 0 ? node[to].lidx : node[to].ridx, node[pto].lidx) + totalcostright[i + 1][0];
	}
	//REP(i, len) printf("%d: leftmost=%d rightmost=%d totalcostleft=%lld/%lld totalcostright=%lld/%lld\n", i, leftmost[i], rightmost[i], totalcostleft[i][0], totalcostleft[i][1], totalcostright[i][0], totalcostright[i][1]);
	REP(i, len) {
		int to = cur[i]; bool canall = leftmost[i] == 0 && rightmost[i] == len - 1;
		REP(side,2) {
			int aidx = i == rightmost[i] ? side == 0 ? node[cur[i]].lidx : node[cur[i]].ridx : node[cur[rightmost[i]]].ridx;
			int bidx = i == leftmost[i] ? side == 0 ? node[cur[i]].lidx : node[cur[i]].ridx : node[cur[leftmost[i]]].lidx;
			ll a = totalcostright[i][side] + (i == leftmost[i] ? 0 : dist(aidx, node[cur[i - 1]].ridx) + totalcostleft[i - 1][1]) + (canall ? outsidecost[at][i != leftmost[i] ? 0 : 1] : 0);
			ll b = totalcostleft[i][side] + (i == rightmost[i] ? 0 : dist(bidx, node[cur[i + 1]].lidx) + totalcostright[i + 1][0]) + (canall ? outsidecost[at][i != rightmost[i] ? 1 : 0] : 0);
			//printf("\t%lld vs %lld\n", a, b);
			outsidecost[to][side] = min(a, b);
		}
	}
	REP(i, len) {
		int to = cur[i];
		dfscalc(to);
	}
}

int makenode(int a, int b, int kind) {
	int ret = nnode++;
	node[ret].lst.clear(); node[ret].lst.PB(a); node[ret].lst.PB(b); node[ret].kind = kind;
	return ret;
}

int merge(int a, int b, int kind) {
	if (node[a].kind == kind && node[b].kind == kind) {
		if (SZ(node[a].lst) >= SZ(node[b].lst)) {
			while (SZ(node[b].lst) != 0) { int x = node[b].lst.front(); node[b].lst.pop_front(); node[a].lst.push_back(x); }
			return a;
		} else {
			while (SZ(node[a].lst) != 0) { int x = node[a].lst.back(); node[a].lst.pop_back(); node[b].lst.push_front(x); }
			return b;
		}
	}
	if (node[a].kind == kind) {
		node[a].lst.push_back(b);
		return a;
	}
	if (node[b].kind == kind) {
		node[b].lst.push_front(a);
		return b;
	}
	return makenode(a, b, kind);
}

int uffind(int x) {
	if (par[x] == x) return par[x];
	return par[x] = uffind(par[x]);
}
void ufunite(int a, int b, int kind) {
	//printf("uniting %d and %d\n", a, b);
	a = uffind(a);
	b = uffind(b);
	int oa = a, ob = b;
	assert(a != b);
	if (sz[a] < sz[b]) swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
	lx[a] = min(lx[a], lx[b]);
	hx[a] = max(hx[a], hx[b]);
	ly[a] = min(ly[a], ly[b]);
	hy[a] = max(hy[a], hy[b]);
	leader[a] = merge(leader[oa], leader[ob], kind);
}

void solve() {
	nxx = 0; REP(i, n) xx[nxx++] = p[i].x; sort(xx, xx + nxx); nxx = unique(xx, xx + nxx) - xx; assert(nxx == n); REP(i, n) p[i].x = lower_bound(xx, xx + nxx, p[i].x) - xx;
	nyy = 0; REP(i, n) yy[nyy++] = p[i].y; sort(yy, yy + nyy); nyy = unique(yy, yy + nyy) - yy; assert(nyy == n); REP(i, n) p[i].y = lower_bound(yy, yy + nyy, p[i].y) - yy;

	nnode = n;
	REP(i, n) {
		int x = p[i].x, y = p[i].y;
		x2idx[x] = i;
		node[x].lst.clear(); node[x].kind = 0;
		par[x] = x, sz[x] = 1, lx[x] = hx[x] = x, ly[x] = hy[x] = y, leader[x] = x;
	}
	REP(i, n) {
		int b = uffind(i);
		while (true) {
			b = uffind(b);
			if (lx[b] - 1 >= 0) {
				int a = uffind(lx[b] - 1);
				assert(hx[a] == lx[b] - 1);
				if (hy[a] == ly[b] - 1) {
					ufunite(a, b, +1);
					continue;
				} else if (ly[a] == hy[b] + 1) {
					ufunite(a, b, -1);
					continue;
				}
			}
			if (hx[b] + 1 < n) {
				int c = uffind(hx[b] + 1);
				assert(lx[c] == hx[b] + 1);
				if (hy[c] == ly[b] - 1) {
					ufunite(b, c, -1);
					continue;
				} else if(ly[c]==hy[b]+1) {
					ufunite(b, c, +1);
					continue;
				}
			}
			break;
		}
	}
	REP(i, nnode) { node[i].vec.clear(); while (SZ(node[i].lst) > 0) { int x = node[i].lst.front(); node[i].lst.pop_front(); node[i].vec.PB(x); } }
	REP(i, nnode) contained[i] = false;
	REP(i, nnode) REPSZ(j, node[i].vec) { int x = node[i].vec[j]; contained[x] = true; }
	//FOR(i, n, nnode) { printf("%d:", i); REPSZ(j, node[i].vec) printf(" %d", node[i].vec[j]); puts(""); }
	REP(i, nnode) if (!contained[i]) { outsidecost[i][0] = outsidecost[i][1] = 0; dfsinit(i); dfscalc(i); }
	REP(i, n) ans[x2idx[i]] = outsidecost[i][0];
}


void run() {
	scanf("%d", &n);
	REP(i, n) scanf("%d%d", &p[i].x, &p[i].y);
	solve();
	REP(i, n) printf("%lld\n", ans[i]);
}

int main() {
	run();
	return 0;
}

```