#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;

Pi P[10010], Q[10010];

vector <int> E[170030];
int scc[170030];
int N;

void addE(int s, int e){
	E[s].pb(e);
	E[e^1].pb(s^1);
}

int xt_add, yt_add, add = (1 << 15);

int S[170030], U[170030], ce, sid;
vector <int> v;

void dfs(int x){
	S[x] = U[x] = ++ce;
	v.pb(x);
	for(int e : E[x]){
		if(S[e] == 0){
			dfs(e);
			U[x] = min(U[x], U[e]);
		}
		else if(scc[e] == 0){
			U[x] = min(U[x], S[e]);
		}
	}
	if(S[x] == U[x]){
		++sid;
		while(1){
			int t = v.back(); v.pop_back();
			scc[t] = sid;
			if(t == x)break;
		}
	}
}

int Do(int max_dis){
	int L[10010], R[10010];
	for(int i=0;i<N;i++){
		L[i] = (int)(lower_bound(P, P+N, Pi(P[i].Fi - max_dis + 1, -1)) - P);
		R[i] = (int)(lower_bound(P, P+N, Pi(P[i].Fi + max_dis - 1, 1e9)) - P - 1);
	}
	xt_add = 2 * N;
	yt_add = 2 * N + 2*add;
	for(int i=0;i<N;i++){
		addE(P[i].Se<<1|1, xt_add + add + 2 * i + 1);
		addE(P[i].Se<<1, xt_add + add + 2 * i);
	}
	
	for(int i=add/2-1;i;i--){
		int li = i * 2, ri = li + 1;
		addE(xt_add + li * 2 + 1, xt_add + i * 2 + 1);
		addE(xt_add + ri * 2 + 1, xt_add + i * 2 + 1);
	}
	
	for(int i=0;i<N;i++){
		int L2[2], R2[2];
		L2[0] = L[i]; R2[0] = i - 1;
		L2[1] = i + 1; R2[1] = R[i];
		rep(u, 2){
			int al = L2[u], ar = R2[u];
			al += add/2, ar += add/2;
			while(al <= ar){
				if(al & 1){
					addE(xt_add + add + 2 * i + 1, xt_add + al * 2);
				}
				if(!(ar & 1)){
					addE(xt_add + add + 2 * i + 1, xt_add + ar * 2);
				}
				al = (al + 1) >> 1;
				ar = (ar - 1) >> 1;
			}
		}
	}
	
	for(int i=0;i<N;i++){
		L[P[i].Se] = (int)(lower_bound(Q, Q+N, Pi(P[i].Fi - max_dis + 1, -1)) - Q);
		R[P[i].Se] = (int)(lower_bound(Q, Q+N, Pi(P[i].Fi + max_dis - 1, 1e9)) - Q - 1);
	}
	
	for(int i=0;i<N;i++){
		int L2[2], R2[2];
		int e = Q[i].Se;
		if(L[e] <= i && i <= R[e]){
			L2[0] = L[e]; R2[0] = i - 1;
			L2[1] = i + 1; R2[1] = R[e];
		}
		else L2[0] = L[e], R2[0] = R[e], L2[1] = 0, R2[1] = -1;
		
		rep(u, 2){
			int al = L2[u], ar = R2[u];
			al += add/2, ar += add/2;
			while(al <= ar){
				if(al & 1){
					addE(yt_add + add + 2 * i, yt_add + al * 2);
				}
				if(!(ar & 1)){
					addE(yt_add + add + 2 * i, yt_add + ar * 2);
				}
				al = (al + 1) >> 1;
				ar = (ar - 1) >> 1;
			}
		}
	}
	
	for(int i=0;i<N;i++){
		L[i] = (int)(lower_bound(Q, Q+N, Pi(Q[i].Fi - max_dis + 1, -1)) - Q);
		R[i] = (int)(lower_bound(Q, Q+N, Pi(Q[i].Fi + max_dis - 1, 1e9)) - Q - 1);
	}
	
	for(int i=0;i<N;i++){
		addE(Q[i].Se<<1, yt_add + add + 2 * i + 1);
		addE(Q[i].Se<<1|1, yt_add + add + 2 * i);
	}
	
	for(int i=add/2-1;i;i--){
		int li = i * 2, ri = li + 1;
		addE(yt_add + li * 2 + 1, yt_add + i * 2 + 1);
		addE(yt_add + ri * 2 + 1, yt_add + i * 2 + 1);
	}
	
	for(int i=0;i<N;i++){
		int L2[2], R2[2];
		L2[0] = L[i]; R2[0] = i - 1;
		L2[1] = i + 1; R2[1] = R[i];
		
		rep(u, 2){
			int al = L2[u], ar = R2[u];
			al += add/2, ar += add/2;
			while(al <= ar){
				if(al & 1){
					addE(yt_add + add + 2 * i + 1, yt_add + al * 2);
				}
				if(!(ar & 1)){
					addE(yt_add + add + 2 * i + 1, yt_add + ar * 2);
				}
				al = (al + 1) >> 1;
				ar = (ar - 1) >> 1;
			}
		}
	}
	
	for(int i=0;i<N;i++){
		L[Q[i].Se] = (int)(lower_bound(P, P+N, Pi(Q[i].Fi - max_dis + 1, -1)) - P);
		R[Q[i].Se] = (int)(lower_bound(P, P+N, Pi(Q[i].Fi + max_dis - 1, 1e9)) - P - 1);
	}
	
	for(int i=0;i<N;i++){
		int L2[2], R2[2];
		int e = P[i].Se;
		if(L[e] <= i && i <= R[e]){
			L2[0] = L[e]; R2[0] = i - 1;
			L2[1] = i + 1; R2[1] = R[e];
		}
		else L2[0] = L[e], R2[0] = R[e], L2[1] = 0, R2[1] = -1;
		
		rep(u, 2){
			int al = L2[u], ar = R2[u];
			al += add/2, ar += add/2;
			while(al <= ar){
				if(al & 1){
					addE(xt_add + add + 2 * i, xt_add + al * 2);
				}
				if(!(ar & 1)){
					addE(xt_add + add + 2 * i, xt_add + ar * 2);
				}
				al = (al + 1) >> 1;
				ar = (ar - 1) >> 1;
			}
		}
	}
	
	int res = 1;
	int END = yt_add+2*add;
	
	for(int i=0;i<END;i++)S[i] = U[i] = scc[i] = 0;
	ce = sid = 0;
	for(int i=0;i<END;i++){
		if(scc[i] == 0)dfs(i);
	}
	
	for(int i=0;i<END/2;i++)if(scc[i<<1] == scc[i<<1|1]){res = 0; break; }
	
	for(int i=0;i<END;i++)E[i].clear();
	return res;
}

void solve(){
	scanf("%d", &N);
	for(int i=0;i<N;i++){
		scanf("%d%d", &P[i].Fi, &Q[i].Fi);
		P[i].Se = Q[i].Se = i;
	}
	sort(P, P+N);
	sort(Q, Q+N);
	int low = 0, high = 1e9 - 1, ans = 1e9;
	 while(low <= high){
		int mid = (low + high) >> 1;
		if(Do(mid))low = mid + 1, ans = mid;
		else high = mid - 1;
	}
	printf("%d\n", ans);
}

int main(){
	int Tc = 1; //scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}

Measured memory_bytes: 29436