#include<bits/stdc++.h>
using namespace std;
#define N 11111116
#define next nxt
int n,k,dx[N],dy[N],x[N],y[N],next[N],p[N],h[N],ans;
struct flag{int x,y,z;}a[N];
bool cmp_x(flag a,flag b){return a.x<b.x;}
bool cmp_y(flag a,flag b){return a.y<b.y;}
bool cmp_z(flag a,flag b){return a.z<b.z;}
void add(int a,int b){
x[++k]=a;y[k]=b;next[k]=p[x[k]];p[x[k]]=k;
x[++k]=b^1;y[++k]=a^1;next[k]=p[x[k]];p[x[k]]=k;
}
void build(int l,int r){
int t=(l+r)|(l<r);
if (l==r) add(2*(n+t),2*dx[l]+1),add(2*(3*n+t),2*dy[l]);
else {
int mid=(l+r)/2,
lc=(l+mid)|(l<mid),
rc=(mid+1+r)|(mid+1<r);
add(2*(n+t),2*(n+lc));
add(2*(n+t),2*(n+rc));
add(2*(3*n+t),2*(3*n+lc));
add(2*(3*n+t),2*(3*n+rc));
build(l,mid);build(mid+1,r);
}
}
void insert(int k,int l,int r,int x,int y,int z){
int t=(l+r)|(l<r);
if (x<=l&&y>=r) add(z,2*(k+t));
else {
int mid=(l+r)/2;
if (x<=mid) insert(k,l,mid,x,y,z);
if (y>=mid+1) insert(k,mid+1,r,x,y,z);
}
}
bool travel(int x,int c1,int c2){
h[x]=c2;
if (h[x]&&h[x^1]) return false;
for (int t=p[x];t;t=next[t])
if (h[y[t]]==c1){
if (!travel(y[t],c1,c2))
return false;
}
return true;
}
bool check(int d){
fill(p+1,p+10*n+1,0);
fill(h+1,h+10*n+1,0);
k=0;build(1,n);
for (int i=1,l=1,r=0;i<=n;i++){
while (l<=n&&a[dx[l]].x<=a[dx[i]].x-d) l++;
while (r<n&&a[dx[r+1]].x<a[dx[i]].x+d) r++;
if (l>r) continue;
if (i<l||i>r) insert(n,1,n,l,r,2*dx[i]);
else {
if (l<i) insert(n,1,n,l,i-1,2*dx[i]);
if (i<r) insert(n,1,n,i+1,r,2*dx[i]);
}
}
for (int i=1,l=1,r=0;i<=n;i++){
while (l<=n&&a[dy[l]].y<=a[dx[i]].x-d) l++;
while (r<n&&a[dy[r+1]].y<a[dx[i]].x+d) r++;
if (l>r) continue;
insert(3*n,1,n,l,r,2*dx[i]);
}
for (int i=1,l=1,r=0;i<=n;i++){
while (l<=n&&a[dx[l]].x<=a[dy[i]].y-d) l++;
while (r<n&&a[dx[r+1]].x<a[dy[i]].y+d) r++;
if (l>r) continue;
insert(n,1,n,l,r,2*dy[i]+1);
}
for (int i=1,l=1,r=0;i<=n;i++){
while (l<=n&&a[dy[l]].y<=a[dy[i]].y-d) l++;
while (r<n&&a[dy[r+1]].y<a[dy[i]].y+d) r++;
if (l>r) continue;
if (i<l||i>r) insert(3*n,1,n,l,r,2*dy[i]+1);
else {
if (l<i) insert(3*n,1,n,l,i-1,2*dy[i]+1);
if (i<r) insert(3*n,1,n,i+1,r,2*dy[i]+1);
}
}
for (int i=1;i<=5*n;i++)
if (!h[2*i]&&!h[2*i+1]){
if (travel(2*i,0,2)) {travel(2*i,2,1);continue;}
travel(2*i,2,0);
if (travel(2*i+1,0,2)) {travel(2*i+1,2,1);continue;};
return false;
}
return true;
}
int read(){
int x=0,f=1;char ch=getchar();
for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-f;
for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
return x*f;
}
int main(){
n=read();
for (int i=1;i<=n;i++){
a[i].x=read();
a[i].y=read();
a[i].z=i;
}
sort(a+1,a+n+1,cmp_x);
for (int i=1;i<=n;i++) dx[i]=a[i].z;
sort(a+1,a+n+1,cmp_y);
for (int i=1;i<=n;i++) dy[i]=a[i].z;
sort(a+1,a+n+1,cmp_z);
for (int k=1<<29;k;k/=2)
if (check(ans+k)) ans+=k;
printf("%d\n",ans);
return 0;
}