#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 9;

int n, x[N], y[N], id1[N], id2[N], r1, r2, ch[N][2], cnt, dfn[N], low[N], stk[N], top, tot, bl[N], tt, rk1[N], rk2[N];
bool vis[N];
vector<int>V[N];

bool cmp1 (int a, int b) { return x[a] < x[b]; }
bool cmp2 (int a, int b) { return y[a] < y[b]; }

#define L ch[x][0]
#define R ch[x][1]

void Build (int &x, int l, int r, int *id, int tj) {
	if (l == r) return void(x = id[l] + tj);
	x = ++cnt;
	int mid = (l + r) >> 1;
	Build(L, l, mid, id, tj);
	Build(R, mid + 1, r, id, tj);
	V[x].emplace_back(L);
	V[x].emplace_back(R);
}

void Min (int &x, int y) { if (x > y) x = y; }

void Tarjan (int x) {
	dfn[x] = low[x] = ++tt;
	stk[++top] = x; vis[x] = 1;
	for (auto v : V[x]) {
		if (!dfn[v]) {
			Tarjan(v);
			Min(low[x], low[v]);
		} else if (vis[v]) Min(low[x], low[v]);
	}
	if (low[x] == dfn[x]) {
		int v = -1; ++tot;
		while (v != x) {
			v = stk[top--];
			bl[v] = tot;
			vis[v] = 0;
		}
	}
}

void Add (int x, int l, int r, int ql, int qr, int d) {
	if (l == ql && r == qr) return V[d].emplace_back(x);
	int mid = (l + r) >> 1;
	if (qr <= mid) Add(L, l, mid, ql, qr, d);
	else if (ql > mid) Add(R, mid + 1, r, ql, qr, d);
	else Add(L, l, mid, ql, mid, d), Add(R, mid + 1, r, mid + 1, qr, d);
}

int find (int *x, int *id, int d) {
	int l = 1, r = n, mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (x[id[mid]] >= d) r = mid - 1;
		else l = mid + 1;
	}
	return l;
}

bool Judge (int S) {
	--S;
	for (int i = 1; i <= cnt; ++i) dfn[i] = 0;
	for (int i = n << 1; i; --i) V[i].clear();
	for (int i = 1, a, b; i <= n; ++i) {
		a = find(x, id1, x[i] - S);
		b = find(x, id1, x[i] + S + 1) - 1;
//		for (int j = a; j <= b; ++j) if (id1[j] != i) {
//			printf("%d %d\n", i, id1[j] + n);
//			V[i].emplace_back(id1[j] + n);
//		}
		if (a <= b) {
			if (a < rk1[i]) Add(r1, 1, n, a, min(rk1[i] - 1, b), i);
			if (rk1[i] < b) Add(r1, 1, n, max(a, rk1[i] + 1), b, i);
		}

		a = find(y, id2, x[i] - S);
		b = find(y, id2, x[i] + S + 1) - 1;
//		for (int j = a; j <= b; ++j) if (id2[j] != i) {
//			printf("%d %d\n", i, id2[j]);
//			V[i].emplace_back(id2[j]);
//		}
		if (a <= b) {
			if (a < rk2[i]) Add(r2, 1, n, a, min(rk2[i] - 1, b), i);
			if (rk2[i] < b) Add(r2, 1, n, max(a, rk2[i] + 1), b, i);
		}

		a = find(x, id1, y[i] - S);
		b = find(x, id1, y[i] + S + 1) - 1;
//		for (int j = a; j <= b; ++j) if (i != id1[j]) {
//			printf("%d %d\n", i + n, id1[j] + n);
//			V[i + n].emplace_back(id1[j] + n);
//		}
		if (a <= b) {
			if (a < rk1[i]) Add(r1, 1, n, a, min(rk1[i] - 1, b), i + n);
			if (rk1[i] < b) Add(r1, 1, n, max(a, rk1[i] + 1), b, i + n);
		}
		
		a = find(y, id2, y[i] - S);
		b = find(y, id2, y[i] + S + 1) - 1;
//		for (int j = a; j <= b; ++j) if (id2[j] != i) {
//			printf("%d %d\n", i + n, id2[j]);
//			V[i + n].emplace_back(id2[j]);
//		}
		if (a <= b) {
			if (a < rk2[i]) Add(r2, 1, n, a, min(rk2[i] - 1, b), i + n);
			if (rk2[i] < b) Add(r2, 1, n, max(a, rk2[i] + 1), b, i + n);
		}
	}
	for (int i = n << 1; i; --i) if (!dfn[i]) Tarjan(i);
	for (int i = 1; i <= n; ++i) if (bl[i] == bl[i + n])
	return 1;
	return 0;
}

int main () {
	scanf("%d", &n); cnt = n << 1;
	for (int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]), id1[i] = id2[i] = i;
	sort(id1 + 1, id1 + n + 1, cmp1);
	sort(id2 + 1, id2 + n + 1, cmp2);
	Build(r1, 1, n, id1, n);
	Build(r2, 1, n, id2, 0);
	for (int i = 1; i <= n; ++i) rk1[id1[i]] = i, rk2[id2[i]] = i;
//	printf("%d\n", Judge(30000)); return 0;
	int l = 1, r = 1e9, mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (Judge(mid)) r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", l - 1);
	return 0;
}

Measured memory_bytes: 14208