#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=200010;
vector<int> g[maxn];
int dfn[maxn],low[maxn],stk[maxn],top,dfs_idx,scc[maxn],scc_idx;
bool in_stk[maxn];
void dfs(int u){
	dfn[u]=low[u]=++dfs_idx;
	stk[++top]=u;
	in_stk[u]=true;
	for(int i=0;i<(int)g[u].size();i++){
		int v=g[u][i];
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
		}else if(in_stk[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int v;
		scc_idx++;
		do{
			v=stk[top--];
			in_stk[v]=false;
			scc[v]=scc_idx;
		}while(v!=u);
	}
}
int n,nor[maxn],inv[maxn],x[maxn],y[maxn];
vector<pii> xs,ys;
void build(int l,int r,int idx){
	if(l==r){
		g[idx+2*n].push_back(nor[xs[l].second]);
		g[idx+2*n+4*n].push_back(inv[xs[l].second]);
		g[idx+2*n+8*n].push_back(nor[ys[l].second]);
		g[idx+2*n+4*n+8*n].push_back(inv[ys[l].second]);
	}else{
		int mid=(l+r)>>1;
		build(l,mid,idx<<1);
		build(mid+1,r,idx<<1|1);
		g[idx+2*n].push_back((idx<<1)+2*n);
		g[idx+2*n].push_back((idx<<1|1)+2*n);
		g[idx+4*n+2*n].push_back((idx<<1)+4*n+2*n);
		g[idx+4*n+2*n].push_back((idx<<1|1)+4*n+2*n);
		g[idx+8*n+2*n].push_back((idx<<1)+8*n+2*n);
		g[idx+8*n+2*n].push_back((idx<<1|1)+8*n+2*n);
		g[idx+4*n+8*n+2*n].push_back((idx<<1)+4*n+8*n+2*n);
		g[idx+4*n+8*n+2*n].push_back((idx<<1|1)+4*n+8*n+2*n);
	}
}
void add_edge(int l,int r,int ql,int qr,int tar,bool is_inv,bool is_y,int idx){
	if(ql>qr) return;
	if(l==ql && r==qr){
		int id=idx+2*n;
		if(is_inv) id+=4*n;
		if(is_y) id+=8*n;
		g[tar].push_back(id);
	}else{
		int mid=(l+r)>>1;
		if(qr<=mid) add_edge(l,mid,ql,qr,tar,is_inv,is_y,idx<<1);
		else if(ql>mid) add_edge(mid+1,r,ql,qr,tar,is_inv,is_y,idx<<1|1);
		else{
			add_edge(l,mid,ql,mid,tar,is_inv,is_y,idx<<1);
			add_edge(mid+1,r,mid+1,qr,tar,is_inv,is_y,idx<<1|1);
		}
	}
}
inline int search(vector<pii>& vc,int tar){
	if(vc[vc.size()-1].first<=tar) return vc.size();
	int l=0,r=vc.size()-1;
	while(l!=r){
		int mid=(l+r)>>1;
		if(vc[mid].first>tar) r=mid;
		else l=mid+1;
	}
	return r;
}
inline int search2(vector<pii>& vc,int tar){
	if(vc[0].first>=tar) return -1;
	int l=0,r=vc.size();
	while(r-l>1){
		int mid=(l+r)>>1;
		if(vc[mid].first<tar) l=mid;
		else r=mid;
	}
	return l;
}
bool check(int limt){
	for(int i=1;i<=18*n;i++){
		g[i].clear();
		dfn[i]=low[i]=0;
	}
	for(int i=1;i<=n;i++)
		nor[i]=i,inv[i]=i+n;
	build(0,n-1,1);
	dfs_idx=scc_idx=0;
	for(int i=1;i<=n;i++){
		int xp=lower_bound(xs.begin(),xs.end(),pii(x[i],i))-xs.begin();
		int yp=lower_bound(ys.begin(),ys.end(),pii(y[i],i))-ys.begin();
		int l=search(xs,x[i]-limt);
		int r=search2(xs,x[i]+limt);
		add_edge(0,n-1,l,min(r,xp-1),nor[i],true,false,1);
		add_edge(0,n-1,max(xp+1,l),r,nor[i],true,false,1);
		l=search(ys,x[i]-limt);
		r=search2(ys,x[i]+limt);
		add_edge(0,n-1,l,min(r,yp-1),nor[i],false,true,1);
		add_edge(0,n-1,max(yp+1,l),r,nor[i],false,true,1);
		l=search(xs,y[i]-limt);
		r=search2(xs,y[i]+limt);
		add_edge(0,n-1,l,min(r,xp-1),inv[i],true,false,1);
		add_edge(0,n-1,max(xp+1,l),r,inv[i],true,false,1);
		l=search(ys,y[i]-limt);
		r=search2(ys,y[i]+limt);
		add_edge(0,n-1,l,min(r,yp-1),inv[i],false,true,1);
		add_edge(0,n-1,max(yp+1,l),r,inv[i],false,true,1);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[nor[i]]) dfs(nor[i]);
		if(!dfn[inv[i]]) dfs(inv[i]);
	}
	// printf("de: %d\n",scc_idx);
	for(int i=1;i<=n;i++){
		if(scc[nor[i]]==scc[inv[i]]){
			return false;
		}
	}
	return true;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",x+i,y+i);
		xs.push_back(pii(x[i],i));
		ys.push_back(pii(y[i],i));
	}
	sort(xs.begin(),xs.end());
	sort(ys.begin(),ys.end());
	// if(check(9)) puts("eê");
	int l=0,r=1000000001;
	while(r-l>1){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	// if(check(9)) puts("eeeeee");
	printf("%d\n",l);
	return 0;
}

Measured memory_bytes: 22144