#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define llu unsigned long long
    #define ld double
    #define llu unsigned long long
    #define rep(i,x,y)  for(ll i=(ll)(x);i<(ll)(y);++i)
    #define For(i,x,y)  for(ll i=(ll)(x);i<=(ll)(y);++i)
    #define FOr(i,x,y)  for(ll i=(ll)(x);i>=(ll)(y);--i)
    #define pi acos(-1) 
    #define mk make_pair
    #define pa pair<ll,ll>
    #define lf else if
    #define IL inline
    #define max(x,y)    ((x)<(y)?(y):(x))
    #define min(x,y)    ((x)<(y)?(x):(y))
    #define sqr(x)      ((x)*(x))
    #define Mul(x,y)    ((x)=1LL*(x)*(y)%mod)
    #define Add(x,y)    ((x)=((x)+(y))%mod)
    #define E(x)        return writeln(x),0
    #define LL			(long long)
    #define p(x)        printf("~%lld~\n",LL(x))
    #define pp(x,y)     printf("~~%lld %lld~~\n",LL(x),LL(y))
    #define ppp(x,y,z)  printf("~~~%lld %lld %lld~~~\n",LL(x),LL(y),LL(z))
    #define pppp(a,b,c,d)	printf("~~~%lld %lld %lld %lld\n",LL(a),LL(b),LL(c),LL(d))
    #define f_in(x)     freopen(x".in","r",stdin)
    #define f_out(x)    freopen(x".out","w",stdout)
    #define open(x)     f_in(x),f_out(x)
    #define fi first
    #define se second
    #define GuYue		puts("\nGuYueNa________________________________________________________________________________")
    #define y1			fafa____
    typedef complex<double> E;
    namespace SHENZHEBEI{
    #ifdef LOCAL
        struct _{_(){freopen("cf.in","r",stdin);}}_; 
    #endif 
    #define NEG 1
        static const int GYN=2333333;
        char SZB[GYN],*S=SZB,*T=SZB;
        inline char gc(){   if (S==T){  T=(S=SZB)+fread(SZB,1,GYN,stdin); if (S==T) return '\n';  }   return *S++;    }
    #if NEG
        inline ll read(){    ll x=0,g=1; char ch=gc();   for (;!isdigit(ch);ch=gc()) if (ch=='-') g=-1;  for (;isdigit(ch);ch=gc())  x=x*10-48+ch;   return x*g; }
        inline void write(ll x){    if (x<0) putchar('-'),x=-x;  if (x>=10)   write(x/10);    putchar(x%10+'0');  }
    #else
        inline ll read(){    ll x=0; char ch=gc();   for (;!isdigit(ch);ch=gc());    for (;isdigit(ch);ch=gc())  x=x*10-48+ch;   return x;   }
        inline void write(ll x){    if (x>=10)   write(x/10);    putchar(x%10+'0');  }
    #endif
        inline char readchar(){ char ch=gc();   for(;isspace(ch);ch=gc());  return ch;  }
        inline ll readstr(char *s){ char ch=gc();   int cur=0;  for(;isspace(ch);ch=gc());      for(;!isspace(ch);ch=gc())  s[cur++]=ch;    s[cur]='\0';    return cur; }
    	void Print(long long *a,int s,int t){For(i,s,t)printf("%lld ",a[i]);puts("");}
    	void Print(int *a,int s,int t){For(i,s,t)printf("%d ",a[i]);puts("");}
    	void Print(char *a,int s,int t){For(i,s,t)putchar(a[i]);puts("");}
    	void writeln(ll x){write(x);putchar('\n');}
    }using namespace SHENZHEBEI;
    const ll N=500010;
    ll id1[N],id2[N],a1[N],a2[N],bel[N],q[N],dfn[N],low[N],mx[N],mn[N],id[N],x[N],y[N],q1[N],q2[N],a[N],ls[N],rs[N],cnt,n,cogito,ind,top,Rt,ans,top1,top2;
    vector<ll>g[N];
    void build(ll l,ll r,ll &p){
    	if (l==r){	p=a[l];	return;	}
    	p=++cnt;
    	ll mid=(l+r)>>1;
    	build(l,mid,ls[p]);	build(mid+1,r,rs[p]);
    	g[p].push_back(ls[p]);	g[p].push_back(rs[p]);
    }
    void clear(){
    	For(i,1,cnt)dfn[i]=low[i]=bel[i]=0,g[i].clear();
    	cnt=cogito=ind=0;
    }
    void AddEdge(ll l,ll r,ll p,ll s,ll t,ll id){
    	if (s<=l&&r<=t){
    		g[id].push_back(p);
    		return;
    	}ll mid=(l+r)/2;
    	if (s<=mid)AddEdge(l,mid,ls[p],s,t,id);
    	if (t>mid)AddEdge(mid+1,r,rs[p],s,t,id);
    }
    void tarjan(ll x){
    	low[q[++top]=x]=dfn[x]=++ind;
    	rep(i,0,g[x].size()){
    		ll to=g[x][i];
    		if (!dfn[to])	tarjan(to),low[x]=min(low[x],low[to]);
    		lf (!bel[to])	low[x]=min(low[x],low[to]);
    	}
    	if (low[x]==dfn[x])	for(++cogito;q[top+1]!=x;)		bel[q[top--]]=cogito;
    }
    bool check(ll len){
    	clear();
    	--len;
    	cnt=n*2;
     
    	For(i,1,n)	a[i]=id1[i]+n;
    	Rt=0;	build(1,n,Rt);
    	For(i,1,n){
    		ll	x1=lower_bound(q1+1,q1+n+2,q1[i]-len)-q1,
    			x2=upper_bound(q1+1,q1+n+2,q1[i]+len)-q1-1;
    		if (x1<i)	AddEdge(1,n,Rt,x1,i-1,id1[i]);
    		if (i<x2)	AddEdge(1,n,Rt,i+1,x2,id1[i]);
     
    		ll	y1=lower_bound(q1+1,q1+n+2,q2[i]-len)-q1,
    			y2=upper_bound(q1+1,q1+n+2,q2[i]+len)-q1-1;
    		if (y1<=y2)	AddEdge(1,n,Rt,y1,y2,id2[i]+n);
     
    	}
    	For(i,1,n)	a[i]=id2[i];
    	Rt=0;	build(1,n,Rt);
    	For(i,1,n){
    		ll	x1=lower_bound(q2+1,q2+n+2,q1[i]-len)-q2,
    			x2=upper_bound(q2+1,q2+n+2,q1[i]+len)-q2-1;
    		if (x1<=x2)	AddEdge(1,n,Rt,x1,x2,id1[i]);
     
    		ll	y1=lower_bound(q2+1,q2+n+2,q2[i]-len)-q2,
    			y2=upper_bound(q2+1,q2+n+2,q2[i]+len)-q2-1;
    		if (y1<i)	AddEdge(1,n,Rt,y1,i-1,id2[i]+n);
    		if (i<y2)	AddEdge(1,n,Rt,i+1,y2,id2[i]+n);
    	}
     
    	For(i,1,cnt)if (!dfn[i])tarjan(i);
    	For(i,1,n)if (bel[i]==bel[i+n])return 0;
    	return 1;
    }
    int main(){
    	mn[0]=2e9;	mx[0]=-2e9;
    	n=read();For(i,1,n)x[i]=read(),y[i]=read(),q1[++top1]=x[i],q2[++top2]=y[i];
    	sort(q1+1,q1+top1+1);sort(q2+1,q2+top2+1);
    	For(i,1,n)a1[i]=a2[i]=i;
    	
    	q1[0]=q2[0]=-2e9;q1[n+1]=q2[n+1]=2e9;
    	For(i,1,n){
    		x[i]=lower_bound(q1+1,q1+top1+1,x[i])-q1,
    		y[i]=lower_bound(q2+1,q2+top2+1,y[i])-q2;
     
    		id1[a1[x[i]]]=i;
    		id2[a2[y[i]]]=i;
     
    		a1[x[i]]++;
    		a2[y[i]]++;
    	}
    //	writeln(check(2));return 0;
    	ll l=1,r=1e9,mid;
    	for(;l<=r;){
    		mid=(l+r)/2;
    		if (check(mid))ans=mid,l=mid+1;
    		else	r=mid-1;
    	}
    	writeln(ans);
    }

Measured memory_bytes: 60416