#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;
}