#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

struct twosat{
    int n;
    vector<vector<int> > adj, radj, scc;
    vector<int> sid, vis, val;
    stack<int> st;
    int cnt;
    twosat(int n): n(n), adj(n), radj(n), sid(n), vis(n), val(n, -1) {}
    void impl(int x, int y){
        adj[x].push_back(y);
        radj[y].push_back(x);
    }
    void vee(int x, int y){ 
        impl(x^1, y);
        impl(y^1, x);
    }
    void nand(int x, int y){
        vee(x^1, y^1);
    }
    void eq(int x, int y){
        impl(x, y);
        impl(y, x);
        impl(x^1, y^1);
        impl(y^1, x^1);
    }
    void tru(int x){
        impl(x^1, x);
    }
    void xoro(int x, int y){
        vee(x, y);
        vee(x^1, y^1);
    }

    void dfs1(int x){
        if(vis[x]++) return;
        for(int i=0;i<adj[x].size();i++) dfs1(adj[x][i]);
        st.push(x);
    }
    void dfs2(int x){
        if(!vis[x]) return;
        vis[x] = 0;
        sid[x] = cnt;
        scc.back().push_back(x);
        for(int i=0;i<radj[x].size();i++) dfs2(radj[x][i]);
    }
    bool two_sat(){
        cnt = 0;
        for(int i=0;i<n;i++) dfs1(i);
        while(!st.empty()){
            int v = st.top();
            st.pop();
            if(vis[v]){
                scc.push_back(vector<int>());
                dfs2(v);
                cnt++;
            }
        }
        for(int i=0;i<n;i+=2){
            if(sid[i] == sid[i+1]) return false;
        }
        vector<int> must(cnt);
        for(int i=0;i<cnt;i++){
            for(int j=0;j<scc[i].size();j++){
                val[scc[i][j]] = must[i];
                must[sid[scc[i][j]^1]] = !must[i];
            }
        }
        return true;
    }
};

void build(int n, int s, int e, vector<pii> &clause){
    if(s == e) return;
    else{
        int mid = (s+e)/2;
        build(n+n, s, mid, clause);
        build(n+n+1, mid+1, e, clause);
        clause.eb(mp(n, n+n));
        clause.eb(mp(n, n+n+1));
    }
}
void query(int n, int s, int e, int l, int r, vector<int> &Q){
    if(s > r || l > e) return;
    if(l <= s && e <= r){
        Q.eb(n);
        return;
    }
    int mid = (s+e)/2;
    query(n+n, s, mid, l, r, Q);
    query(n+n+1, mid+1, e, l, r, Q);
}

pii p[2][10005];
int n;
int idx1[10005], idx2[10005];

int findLeft(int i, int x){
    int lo = 1, hi = n, ans = n+1;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        if(p[i][mid].fi >= x) ans = mid, hi = mid-1;
        else lo = mid+1;
    }
    return ans;
}
int findRight(int i, int x){
    int lo = 1, hi = n, ans = 0;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        if(p[i][mid].fi <= x) ans = mid, lo = mid+1;
        else hi = mid-1;
    }
    return ans;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        int x, y;
        scanf("%d%d", &x, &y);
        p[0][i] = mp(x, i);
        p[1][i] = mp(y, i);
    }
    sort(p[0]+1, p[0]+1+n);
    sort(p[1]+1, p[1]+1+n);
    for(int i=1;i<=n;i++) idx1[p[0][i].se] = i, idx2[p[1][i].se] = i;

    int lo = 1, hi = 1e9, ans = 0;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        int D = mid;

        twosat sat(16*n+10);
        vector<pii> clause;
        build(1, 1, n, clause);
        for(int i=0;i<sz(clause);i++){
            int x = clause[i].fi*2, y = clause[i].se*2;
            sat.impl(y, x);
            x = (clause[i].fi+4*n)*2, y = (clause[i].se+4*n)*2;
            sat.impl(y, x);
        }

        for(int i=1;i<=n;i++){
            vector<int> Q1, Q2, Q3;
            int l = findLeft(0, p[0][i].fi - D + 1);
            int r = findRight(0, p[0][i].fi + D - 1);
            if(l <= r){
                int idx = idx1[p[0][i].se];
                Q1.clear(), Q2.clear(), Q3.clear();
                if(l <= idx && idx <= r){
                    query(1, 1, n, i, i, Q1);
                    if(idx != l) query(1, 1, n, l, idx-1, Q2);
                    if(idx != r) query(1, 1, n, idx+1, r, Q3);
                }
                else{
                    query(1, 1, n, i, i, Q1);
                    query(1, 1, n, l, r, Q2);
                }
                for(int i=0;i<sz(Q2);i++) sat.nand(Q1[0]*2, Q2[i]*2);
                for(int i=0;i<sz(Q3);i++) sat.nand(Q1[0]*2, Q3[i]*2);
            }

            l = findLeft(1, p[0][i].fi - D + 1);
            r = findRight(1, p[0][i].fi + D - 1);
            if(l <= r){
                int idx = idx2[p[0][i].se];
                Q1.clear(), Q2.clear(), Q3.clear();
                if(l <= idx && idx <= r){
                    query(1, 1, n, i, i, Q1);
                    if(idx != l) query(1, 1, n, l, idx-1, Q2);
                    if(idx != r) query(1, 1, n, idx+1, r, Q3);
                }
                else{
                    query(1, 1, n, i, i, Q1);
                    query(1, 1, n, l, r, Q2);
                }
                for(int i=0;i<sz(Q2);i++) sat.nand(Q1[0]*2, (Q2[i]+4*n)*2);
                for(int i=0;i<sz(Q3);i++) sat.nand(Q1[0]*2, (Q3[i]+4*n)*2);
            }


            l = findLeft(0, p[1][i].fi - D + 1);
            r = findRight(0, p[1][i].fi + D - 1);
            if(l <= r){
                int idx = idx1[p[1][i].se];
                Q1.clear(), Q2.clear(), Q3.clear();
                if(l <= idx && idx <= r){
                    query(1, 1, n, i, i, Q1);
                    if(idx != l) query(1, 1, n, l, idx-1, Q2);
                    if(idx != r) query(1, 1, n, idx+1, r, Q3);
                }
                else{
                    query(1, 1, n, i, i, Q1);
                    query(1, 1, n, l, r, Q2);
                }
                for(int i=0;i<sz(Q2);i++) sat.nand((Q1[0]+4*n)*2, Q2[i]*2);
                for(int i=0;i<sz(Q3);i++) sat.nand((Q1[0]+4*n)*2, Q3[i]*2);
            }

            l = findLeft(1, p[1][i].fi - D + 1);
            r = findRight(1, p[1][i].fi + D - 1);
            if(l <= r){
                int idx = idx2[p[1][i].se];
                Q1.clear(), Q2.clear(), Q3.clear();
                if(l <= idx && idx <= r){
                    query(1, 1, n, i, i, Q1);
                    if(idx != l) query(1, 1, n, l, idx-1, Q2);
                    if(idx != r) query(1, 1, n, idx+1, r, Q3);
                }
                else{
                    query(1, 1, n, i, i, Q1);
                    query(1, 1, n, l, r, Q2);
                }
                for(int i=0;i<sz(Q2);i++) sat.nand((Q1[0]+4*n)*2, (Q2[i]+4*n)*2);
                for(int i=0;i<sz(Q3);i++) sat.nand((Q1[0]+4*n)*2, (Q3[i]+4*n)*2);
            }

            Q1.clear(), Q2.clear();
            query(1, 1, n, i, i, Q1);
            query(1, 1, n, idx2[p[0][i].se], idx2[p[0][i].se], Q2);

            sat.xoro(Q1[0]*2, (Q2[0]+4*n)*2);
        }
        int s = sat.two_sat();
        if(s == 1) ans = mid, lo = mid+1;
        else hi = mid-1;
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 46856