#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int M=3e6;
const int K=1e5;
const LL P=1e8;
int n,N=0;
struct data {
    LL x,y;
    int num;
}a[K+10],b[K+10],c[K+10];
bool cmpx(data p,data q) {
    return p.x<q.x;
}
bool cmpy(data p,data q) {
    return p.y<q.y;
}
bool cmp(data p,data q) {
    return p.num<q.num;
}
LL Abs(LL x) {
    if (x<0) return -x;
    return x;
}
namespace sat {
    int n,dx,tot,cnt,now;
    int head[M+10],dfn[M+10],ins[M+10],ans[M+10],s[M+10],low[M+10];
    struct data {
        int next,num;
    }edge[M+10];
    void clear() {
        memset(head,-1,sizeof(head));
        dx=tot=cnt=now=0;
    }
    void Add(int u,int v) {
        edge[++tot].next=head[u];
        edge[tot].num=v;
        head[u]=tot;
    }
    void Tarjan(int x) {
        low[x]=dfn[x]=++dx;
        s[++cnt]=x;
        ins[x]=1;
        for (int i=head[x];i!=-1;i=edge[i].next) {
            int kx=edge[i].num;
            if (dfn[kx]) {
                if (ins[kx]) low[x]=min(low[x],dfn[kx]);
                continue;
            }
            Tarjan(kx);
            low[x]=min(low[x],low[kx]);
        }
        if (low[x]<dfn[x]) return;
        ++now;
        while (s[cnt]!=x) {
            ans[s[cnt]]=now;
            ins[s[cnt]]=0;
            cnt--;
        }
        ans[x]=now;
        ins[x]=0;
        cnt--;
    }
    bool work() {
        for (int i=1;i<=n*2;i++) dfn[i]=ins[i]=ans[i]=0;
        for (int i=1;i<=n*2;i++)
            if (!dfn[i]) Tarjan(i);
        for (int i=1;i<=n;i++)
            if (ans[i*2-1]!=0&&ans[i*2-1]==ans[i*2]) return 0;
        return 1;
    }
}
struct node {
    int l,r;
}t1[M+10],t2[M+10];
void build1(int x,int l,int r) {
    N=max(N,x);
    t1[x].l=l;
    t1[x].r=r;
    if (l==r) {
        sat::Add((n+x)*2-1,b[l].num*2);
        sat::Add(b[l].num*2-1,(n+x)*2);
        return;
    }
    int mid=(l+r)/2;
    build1(x*2,l,mid);
    build1(x*2+1,mid+1,r);
    sat::Add((n+x)*2-1,(n+x*2)*2-1);
    sat::Add((n+x*2)*2,(n+x)*2);
    sat::Add((n+x)*2-1,(n+x*2+1)*2-1);
    sat::Add((n+x*2+1)*2,(n+x)*2);
}
void build2(int x,int l,int r) {
    t2[x].l=l;
    t2[x].r=r;
    if (l==r) {
        sat::Add((n+N+x)*2-1,c[l].num*2-1);
        sat::Add(c[l].num*2,(n+N+x)*2);
        return;
    }
    int mid=(l+r)/2;
    build2(x*2,l,mid);
    build2(x*2+1,mid+1,r);
    sat::Add((n+N+x)*2-1,(n+N+x*2)*2-1);
    sat::Add((n+N+x*2)*2,(n+N+x)*2);
    sat::Add((n+N+x)*2-1,(n+N+x*2+1)*2-1);
    sat::Add((n+N+x*2+1)*2,(n+N+x)*2);
}
void Add1(int i,LL l,LL r,LL x,LL y) {
    LL nowl=b[t1[i].l].x,nowr=b[t1[i].r].x;
    if (nowl>r||nowr<l) return;
    if (nowl>=l&&nowr<=r) {
        sat::Add(x,(n+i)*2-1);
        sat::Add((n+i)*2,y);
        return;
    }
    Add1(i*2,l,r,x,y);
    Add1(i*2+1,l,r,x,y);
}
void Add2(int i,LL l,LL r,LL x,LL y) {
    LL nowl=c[t2[i].l].y,nowr=c[t2[i].r].y;
    if (nowl>r||nowr<l) return;
    if (nowl>=l&&nowr<=r) {
        sat::Add(x,(n+N+i)*2-1);
        sat::Add((n+N+i)*2,y);
        return;
    }
    Add2(i*2,l,r,x,y);
    Add2(i*2+1,l,r,x,y);
}
bool check(LL x) {
    if (x==0) return 1;
    N=0;
    sat::clear();
    build1(1,1,n);
    build2(1,1,n);
    for (int i=1;i<=n;i++) {
        LL nowx=a[i].x,nowy=a[i].y;
        LL nowl=nowx-x,nowr=nowx+x;
        Add1(1,nowl,nowx-1,a[i].num*2-1,a[i].num*2);
        Add1(1,nowx+1,nowr,a[i].num*2-1,a[i].num*2);
        Add2(1,nowl,nowr,a[i].num*2-1,a[i].num*2);
        nowl=nowy-x+1,nowr=nowy+x-1;
        Add1(1,nowl,nowr,a[i].num*2,a[i].num*2-1);
        Add2(1,nowl,nowy-1,a[i].num*2,a[i].num*2-1);
        Add2(1,nowy+1,nowr,a[i].num*2,a[i].num*2-1);
    }
    sat::n=n+N*2;
    if (sat::work()) return 1;
    return 0;
}
int main() {
    //    freopen("windmills.in","r",stdin);
    //    freopen("windmills.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%lld%lld",&a[i].x,&a[i].y);
        a[i].num=i;
    }
    sort(a+1,a+n+1,cmpx);
    for (int i=1;i<=n;i++)
        if (i!=1&&a[i].x==a[i-1].x/P) a[i].x=a[i-1].x+1;
        else a[i].x*=P;
    sort(a+1,a+n+1,cmpy);
    for (int i=1;i<=n;i++)
        if (i!=1&&a[i].y==a[i-1].y/P) a[i].y=a[i-1].y+1;
        else a[i].y*=P;
    sort(a+1,a+n+1,cmpx);
    for (int i=1;i<=n;i++) b[i]=a[i];
    sort(a+1,a+n+1,cmpy);
    for (int i=1;i<=n;i++) c[i]=a[i];
    sort(a+1,a+n+1,cmp);
    LL l=0,r=1e9;
    if (!check(1000000ll*P-1e4)) r=1e6;
    if (!check(10000ll*P-1e4)) r=1e4;
    while (l<r) {
        LL mid=(l+r+1)/2;
        if (check(mid*P-1e4)) l=mid;
        else r=mid-1;
    }
    printf("%lld\n",l);
    return 0;
}


Measured memory_bytes: 54656