#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 50, INF = 0x3f3f3f3f;
const double alpha = 0.75;

inline int read () {
	register int x = 0, w = 1;
	register char ch = getchar ();
	for (; ch < '0' || ch > '9'; ch = getchar ()) if (ch == '-') w = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar ()) x = x * 10 + ch - '0';
	return x * w;
}

inline void write (register int x) {
	if (x / 10) write (x / 10);
	putchar (x % 10 + '0');
}

int n, m, now, top, root, nodecnt, ans, st[maxn];

struct Manhattan_Dis { // 曼哈顿距离
	
	struct Node {
		int lson, rson, size, d[2], maxx[2], minn[2];
		Node () {}
		Node (register int a, register int b) { d[0] = a, d[1] = b, lson = rson = 0; }
		inline bool operator < (const Node &x) const { return d[now] < x.d[now]; }
	} a[maxn], tree[maxn];

	inline int newnode () { return top ? st[top --] : ++ nodecnt; }

	inline void Pushup (register int rt) {
		register int lson = tree[rt].lson, rson = tree[rt].rson;
		tree[rt].size = tree[lson].size + tree[rson].size + 1;	
		for (register int i = 0; i < 2; i ++) {
			tree[rt].maxx[i] = tree[rt].minn[i] = tree[rt].d[i];
			if (lson) tree[rt].maxx[i] = max (tree[rt].maxx[i], tree[lson].maxx[i]), tree[rt].minn[i] = min (tree[rt].minn[i], tree[lson].minn[i]);
			if (rson) tree[rt].maxx[i] = max (tree[rt].maxx[i], tree[rson].maxx[i]), tree[rt].minn[i] = min (tree[rt].minn[i], tree[rson].minn[i]);
		}
	}

	inline int Build (register int l, register int r, register int opt) {
		now = opt;
		register int rt = newnode (), mid = (l + r) >> 1;
		nth_element (a + l, a + mid, a + r + 1), tree[rt] = a[mid];
		if (l < mid) tree[rt].lson = Build (l, mid - 1, ! opt);
		if (r > mid) tree[rt].rson = Build (mid + 1, r, ! opt);
		return Pushup (rt), rt;
	}

	inline void Unflod (register int rt, register int num) {
		register int lson = tree[rt].lson, rson = tree[rt].rson;
		if (lson) Unflod (lson, num);
		register int now = num + tree[lson].size + 1;
		a[now] = Node (tree[rt].d[0], tree[rt].d[1]), st[++ top] = rt;
		if (rson) Unflod (rson, now);
	}

	inline void Check (register int &rt, register int opt) {
		register int lson = tree[rt].lson, rson = tree[rt].rson;
		if (tree[lson].size >= tree[rt].size * alpha || tree[rson].size >= tree[rt].size * alpha) Unflod (rt, 0), rt = Build (1, tree[rt].size, opt);
	}

	inline void Insert (register Node u, register int &rt, register int opt) {
		if (! rt) return rt = newnode (), tree[rt] = u, Pushup (rt), void ();
		if (u.d[now] <= tree[rt].d[now]) Insert (u, tree[rt].lson, ! opt);
		else Insert (u, tree[rt].rson, ! opt);
		Pushup (rt), Check (rt, opt);
	}

	inline int Getdis (register int x0, register int x1, register int y0, register int y1) { return abs (x0 - x1) + abs (y0 - y1); }

	inline int Est1 (register int rt, register int x, register int y) {
		register int dis1 = Getdis (x, tree[rt].maxx[0], y, tree[rt].maxx[1]);
		register int dis2 = Getdis (x, tree[rt].maxx[0], y, tree[rt].minn[1]);
		register int dis3 = Getdis (x, tree[rt].minn[0], y, tree[rt].maxx[1]);
		register int dis4 = Getdis (x, tree[rt].minn[0], y, tree[rt].minn[1]);
		return max (dis1, max (dis2, max (dis3, dis4)));
	}

	inline int Est2 (register int rt, register int x, register int y) {
		register int dis1 = min (abs (x - tree[rt].maxx[0]), abs (x - tree[rt].minn[0]));
		register int dis2 = min (abs (y - tree[rt].maxx[1]), abs (y - tree[rt].minn[1]));
		if (tree[rt].minn[0] <= x && x <= tree[rt].maxx[0]) dis1 = 0;
		if (tree[rt].minn[1] <= y && y <= tree[rt].maxx[1]) dis2 = 0;
		return dis1 + dis2;
	}

	inline void Query1 (register int rt, register int x, register int y) { // 询问最远点
		ans = max (ans, Getdis (x, tree[rt].d[0], y, tree[rt].d[1]));
		register int lson = tree[rt].lson, rson = tree[rt].rson;
		if (! lson && ! rson) return;
		register int tmp1 = - INF, tmp2 = - INF;
		if (lson) tmp1 = Est1 (lson, x, y);
		if (rson) tmp2 = Est1 (rson, x, y);
		if (tmp1 > tmp2) {
			if (tmp1 > ans) Query1 (lson, x, y);
			if (tmp2 > ans) Query1 (rson, x, y);
		} else {
			if (tmp2 > ans) Query1 (rson, x, y);
			if (tmp1 > ans) Query1 (lson, x, y);
		}
	}

	inline void Query2 (register int rt, register int x, register int y) { // 询问最近点
		ans = min (ans, Getdis (x, tree[rt].d[0], y, tree[rt].d[1]));
		register int lson = tree[rt].lson, rson = tree[rt].rson;
		if (! lson && ! rson) return;
		register int tmp1 = INF, tmp2 = INF;
		if (lson) tmp1 = Est2 (lson, x, y);
		if (rson) tmp2 = Est2 (rson, x, y);
		if (tmp1 < tmp2) {
			if (tmp1 <= ans) Query2 (lson, x, y);
			if (tmp2 <= ans) Query2 (rson, x, y);
		} else {
			if (tmp2 <= ans) Query2 (rson, x, y);
			if (tmp1 <= ans) Query2 (lson, x, y);
		}
	}
	
};

int main () {
	
	return 0;
}