#include<bits/stdc++.h>

#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define pb push_back
#define len(x) (int)(x).size()
#define mkp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;

const int NN = 2e5;
const int N = 4e4 + 10 , inf = 1e9;
pii cord[N];
array<int , 2>vert[N];
vector<int>g[NN] , gg[NN];
void impli(int u , int v){
    g[u].pb(v);
}

int seg[4*N] , f[N];
void build(int v , int tl , int tr , int &cnt){
    if(tl == tr){
        seg[v] = f[tl];
        return;
    }
    seg[v] = cnt++;
    int mid = (tl + tr) >> 1 , v1 = v << 1;
    build(v1 , tl , mid , cnt);
    build(v1 | 1 , mid + 1 , tr , cnt);
    impli(seg[v] , seg[v1]);
    impli(seg[v] , seg[v1|1]);
}
void LineImpli(int v , int tl , int tr,  int l , int r , int V){
    if(tl == l && tr == r){
        impli(V , seg[v]);
        return;
    }
    int mid = (tl + tr) >> 1 , v1=  v << 1;
    if(l <= mid)
        LineImpli(v1 , tl , mid , l , min(r , mid) , V);
    if(r > mid)
        LineImpli(v1|1 , mid + 1 , tr , max(l , mid + 1) , r , V);
}

int comp[NN] , topsort[NN];
void dfs(int v , int &lst){
    comp[v] = 1;
    for(auto u : g[v])
        if(!comp[u])
            dfs(u , lst);
    topsort[lst++] = v;
}
void compFind(int v, int color){
    comp[v] = color;
    for(auto u : gg[v]){
        if(!comp[u])
            compFind(u , color);
    }
}

bool satisfiable(int n){

    for(int i = 0 ; i < NN; ++i)
        gg[i].clear();
    for(int i = 0 ; i < NN; ++i)
        for(auto u : g[i])
            gg[u].pb(i);
    fill(comp , comp + NN , 0);
    int lst = 0;
    for(int i = 0  ; i < NN; ++i)
        if(!comp[i])
            dfs(i , lst);
    fill(comp , comp + NN , 0);
    int cur = 1;
    for(int i = lst - 1; i >= 0; --i){
        int to = topsort[i];
        if(!comp[to]){
            compFind(to , cur++);
        }
    }
    /// check it out
    for(int i = 0; i < n ;++i){
        if(comp[vert[2*i][0]] == comp[vert[2*i][1]])
            return false;
        if(comp[vert[2*i+1][0]] == comp[vert[2*i+1][1]])
            return false;
    }
    return true;
}
signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    /// lulz
    int n;cin >> n;
    for(int i =  0 ; i < n ;++i)
        cin >> cord[i].fi >> cord[i].se;
    int cnt = 0;
    for(int i = 0 ; i < n; ++i){
        vert[2*i] = {cnt , cnt+1};
        vert[2*i+1] = {cnt+2,cnt+3};
        cnt += 4;
    }


    vector<pii>bydist[2];
    for(int i = 0 ;  i < n; ++i){
        for(int bt = 0; bt < 2; ++bt){
            bydist[bt].pb({cord[i].fi, vert[2*i][bt]});
            bydist[bt].pb({cord[i].se, vert[2*i+1][bt]});
        }
    }
    sort(all(bydist[0])) , sort(all(bydist[1]));
    for(int i = 0; i < len(bydist[0]); ++i){
        f[i] = bydist[0][i].se;
    }
    int BYD = len(bydist[0]);
    int l  = 0 , r = (int)1e9 + 1;


//    l = 1 , r = 2;
    while(l != r){
        int mid = (l + r) >> 1;


        /// let us mid = 4
        for(int i = 0  ; i < NN; ++i)
            g[i].clear();
        for(int i = 0 ; i < n; ++i){
            impli(vert[2*i][0] , vert[2*i+1][1]);
            impli(vert[2*i+1][0] , vert[2*i][1]);
            impli(vert[2*i][1] , vert[2*i+1][0]);
            impli(vert[2*i+1][1] , vert[2*i][0]);
        }
        ///
        int cnt = 4*n;

////        cout << " 1\n";
        build(1 , 0 , BYD-1 , cnt);
////        cout << " 2\n";
        for(int i = 0; i < len(bydist[1]); ++i){
            int X , V;
            tie(X , V) = bydist[1][i];
            int L = upper_bound(all(bydist[0]) , mkp(X - mid , inf)) - bydist[0].begin();
            int R = lower_bound(all(bydist[0]) , mkp(X, V-1)) - bydist[0].begin() - 1;
            if(L <= R){
//                for(int j = L; j <= R; ++j){
//                    impli(V , f[j]);
//                }
                LineImpli(1 , 0 , BYD-1 , L , R , V);
            }
            L = upper_bound(all(bydist[0]) , mkp(X, V-1)) - bydist[0].begin();
            R = lower_bound(all(bydist[0]) , mkp(X + mid, -1)) - bydist[0].begin() - 1;
            if(L <= R){
//                for(int j = L; j <= R; ++j){
//                    impli(V , f[j]);
//                }
                LineImpli(1 , 0 , BYD-1 , L , R , V);
            }


        }
////        cout << " 3\n";
//        /// condens
//        cout << " MID " << mid << '\n';
//        cout << " GRAPH \n";
//        for(int i = 0 ;  i < N; ++i)
//            for(auto u : g[i])
//                cout << " EDGE " << i << ' ' << u << '\n';
//        cout << '\n';


        bool kek = satisfiable(n);



        if(kek){
            if(l + 1 == r) l = r;
            else l = mid;
        }else r = mid;

    }
    cout << r - 1;
    return 0;
}


Measured memory_bytes: 31772