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>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

struct PermutationTree{

	static const int N = 400007;
	#define ll long long
	#define ii pair<ll,ll>
	#define iii pair<ii,ll>
	#define fi first
	#define se second

	#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))


	struct node{
		int s,e,m;
		ll val=0,lazy=0;
		node *l,*r;
		
		node (int _s,int _e){
			s=_s,e=_e,m=s+e>>1;
			
			if (s!=e){
				l=new node(s,m);
				r=new node(m+1,e);
			}
		}
		
		void propo(){
			if (lazy){
				val+=lazy;
				if (s!=e){
					l->lazy+=lazy;
					r->lazy+=lazy;
				}
				lazy=0;
			}
		}
		
		void update(int i,int j,ll k){
			if (s==i && e==j) lazy+=k;
			else{
				if (j<=m) l->update(i,j,k);
				else if (m<i) r->update(i,j,k);
				else l->update(i,m,k),r->update(m+1,j,k);
				
				l->propo(),r->propo();
				val=min(l->val,r->val);
			}
		}
		
		ll query(int i,int j){
			propo();
			
			if (s==i && e==j) return val;
			else if (j<=m) return l->query(i,j);
			else if (m<i) return r->query(i,j);
			else return min(l->query(i,m),r->query(m+1,j));
		}
	};

	int n,q;
	int arr[N];
	ii range[N];
	ii span[N];
	vector<int> children[N];
	int parent[N];
	int typ[N];
	int idx; //new index to assign to nodes

	ii get_range(ii i,ii j){
		return ii(min(i.fi,j.fi),max(i.se,j.se));
	}

	void add_edge(int u,int v){ //u is parent of v
		parent[v]=u;
		children[u].push_back(v);
	}

	bool adj(int i,int j){
		return range[i].se==range[j].fi-1;
	}

	int length(int i){
		return range[i].se-range[i].fi+1;
	}

	void build(vector<int> v){
		n = v.size();
		for (int i = 0; i < n; ++i) arr[i] = v[i];
		idx=n;
		memset(parent,-1,sizeof(parent));
		
		node *root=new node(0,N);
		vector<int> mx={-1},mn={-1}; //stacks for max and min
		
		vector<int> nodes; //stack of cut and join nodes
		
		rep(x,0,n){
			//update Q values
			while (mx.back()!=-1 && arr[mx.back()]<arr[x]){
				int temp=mx.back();
				mx.pop_back();
				root->update(mx.back()+1,temp,arr[x]-arr[temp]);
			}
			mx.push_back(x);
			
			while (mn.back()!=-1 && arr[mn.back()]>arr[x]){
				int temp=mn.back();
				mn.pop_back();
				root->update(mn.back()+1,temp,arr[temp]-arr[x]);
			}
			mn.push_back(x);
			
			//handle stack updates
			range[x]=ii(arr[x],arr[x]);
			span[x]=ii(x,x);
			int curr=x;
			
			while (true){
				if (!nodes.empty() && (adj(nodes.back(),curr) || adj(curr,nodes.back()))){
					if ((adj(nodes.back(),curr) && typ[nodes.back()]==1)||
					  (adj(curr,nodes.back()) && typ[nodes.back()]==2)){
						add_edge(nodes.back(),curr);
						
						range[nodes.back()]=get_range(range[nodes.back()],range[curr]);
						span[nodes.back()]=get_range(span[nodes.back()],span[curr]);
						
						curr=nodes.back();
						nodes.pop_back();
					}
					else{ //make a new join node
						typ[idx]=(adj(nodes.back(),curr) ? 1:2);
						add_edge(idx,nodes.back());
						add_edge(idx,curr);
						
						range[idx]=get_range(range[nodes.back()],range[curr]);
						span[idx]=get_range(span[nodes.back()],span[curr]);
						
						nodes.pop_back();
						curr=idx++;
					}
				}
				else if (x-(length(curr)-1) && root->query(0,x-length(curr))==0){
					int len=length(curr);
					ii r=range[curr];
					ii s=span[curr];
					
					add_edge(idx,curr);
					
					do{
						len+=length(nodes.back());
						r=get_range(r,range[nodes.back()]);
						s=get_range(s,span[nodes.back()]);
						
						add_edge(idx,nodes.back());
						
						nodes.pop_back();
					} while (r.se-r.fi+1!=len);
					
					reverse(all(children[idx]));
					range[idx]=r;
					span[idx]=s;
					curr=idx++;
				}
				else{
					break;
				}
			}
			
			nodes.push_back(curr);
			root->update(0,x,-1);
		}
	}

	pair<int, int> get_range(int x) {
		return range[x];
	}

	pair<int, int> get_seg(int x) {
		return span[x];
	}

	vector<int> get_sons(int x) {
		return children[x];
	}

	bool if_cut(int x) {
		auto var = get_sons(x);

		vector<pair<int, int> > tet;
		for (auto x : var) tet.pb(range[x]);

		auto ctet = tet;
		sort(all(tet));

		if (tet == ctet) return true;
		reverse(all(tet));
		if (tet == ctet) return true;
		return false;

	}

	int get_root() {
		int cur = 0;
		while (parent[cur] != -1){
			cur = parent[cur];
		}
		return cur;
	}

	int get_parent(int x) {
		return parent[x];
	}

};

PermutationTree tree;

vector<pair<int, int> > arr;
map<pair<int, int>, int> tet;

vector<ll> ans;

int get_dist(pair<int, int> a, pair<int, int> b) {
	return abs(a.x-b.x) + abs(a.y-b.y);
}

void solve(int root, ll x, ll y) {
	auto res = tree.get_seg(root);
	//cout << res.x << " " << res.y << " " << x << " " << y << endl;
	if (res.x == res.y) {
		ans[tet[arr[res.x]]] = min(x, y);
		return;
	}

	auto children = tree.get_sons(root);

	if (!tree.if_cut(root)) {
		for (auto x : children) {
			solve(x, 0, 0);
		}
		return;
	}

	int sz = children.size();

	vector<int> take_right(sz), take_left(sz);
	vector<int> cnt_left(sz), cnt_right(sz);

	for (int i = 0; i < sz; ++i) {
		auto cur = tree.get_seg(children[i]);
		if (cur.x != cur.y) take_left[i] = 0, cnt_left[i] = 0;
		else {
			take_left[i] = 1;
			cnt_left[i] = cur.y  - cur.x+1;
			if (i > 0) {
				take_left[i] += take_left[i-1];
				cnt_left[i] += cnt_left[i-1];
			}
		}
	}

	reverse(all(children));

	for (int i = 0; i < sz; ++i) {
		auto cur = tree.get_seg(children[i]);
		if (cur.x != cur.y) {
			take_right[i] = 0;
			cnt_right[i] = 0;
		}
		else {
			take_right[i] = 1;
			cnt_right[i] = cur.y  - cur.x+1;
			if (i > 0) {
				take_right[i] += take_right[i-1];
				cnt_right[i] += cnt_right[i-1];
			}
		}
	}

	reverse(all(children));
	reverse(all(take_right));
	reverse(all(cnt_right));

	//cout << res.x << " " << res.y << " " << x << " " << y << endl;

	for (int i = 0; i < children.size(); ++i) {

		int L = tree.get_seg(children[i]).x;
		int R = tree.get_seg(children[i]).y;

		ll a = 1e18, b = 1e18;

		int tl = 0, tr = 0, cl = 0, cr = 0;

		if (i > 0) {
			cl = cnt_left[i-1];
			tl = take_left[i-1];
		}
		if (i + 1 < children.size()) {
			cr = cnt_right[i+1];
			tr = take_right[i+1];
		}

		ll left_sign = 0, right_sign = 0;
		if (cr+cl+1 == children.size()) left_sign = x, right_sign = y;

		int e = L-tl, f = R+tr;
		if (cl==0) e = R;
		if (cr==0) f = L;

		a = min({a, right_sign + get_dist(arr[L], arr[L - tl]) + get_dist(arr[L-tl], arr[R+tr]) - tl - tr, left_sign + get_dist(arr[L], arr[f]) + get_dist(arr[L-tl], arr[f]) - tl - tr});
		b = min({b, right_sign + get_dist(arr[R], arr[e]) + get_dist(arr[e], arr[R+tr]) - tl - tr, left_sign + get_dist(arr[R], arr[R+tr]) + get_dist(arr[L-tl], arr[R+tr]) - tl - tr});

		//cout << a << " " << b << " " << L << " " << R << " " << tl << " " << tr << endl;

		solve(children[i], a, b);

	}

}

int main(){
#ifdef LOCAL
	freopen("K_input.txt", "r", stdin);
	//freopen("K_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	ans.assign(n, -1);

	vector<int> ys;

	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		ys.pb(y);
		arr.pb(mp(x, y));
		tet[mp(x, y)] = i;
	}

	sort(all(arr));
	sort(all(ys));

	map<int, int> tet;
	for (int i = 0; i < ys.size(); ++i) tet[ys[i]] = i;

	vector<int> v(n);

	for (int i =0; i < n; ++i) {
		v[i] = tet[arr[i].y];
		//cout << v[i] << " ";
	}

	tree.build(v);
	int root = tree.get_root();

	solve(root, 0, 0);

	for (auto x : ans) {
		cout << x << '\n';
	}


}