//#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC target("avx2,avx")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln = '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename T>
struct edge {
    int src,to;
    T cost;
    int id;

    edge(){}
    edge(int to, T cost) : src(-1), to(to), cost(cost), id(-1) {}
    edge(int src, int to, T cost) : src(src), to(to), cost(cost), id(-1) {}
    edge(int src, int to, T cost, int id) : src(src), to(to), cost(cost), id(id) {}
    bool operator<(const edge &e) const {return cost < e.cost;}
};

struct StronglyConnectedComponent {
    //T:強連結成分をトポロジカルソートしたグラフ C:強連結成分の内訳
    vector<vector<int>> G,R,T,C;
    vector<int> vs,used,blg;
    StronglyConnectedComponent() {}
    StronglyConnectedComponent(int N) : G(N), R(N), used(N), blg(N) {}

    void add_edge(int u,int v) {
        G[u].emplace_back(v);
        R[v].emplace_back(u);
    }

    void dfs(int v){
        used[v] = 1;
        for(int u:G[v]) {
            if(!used[u]) dfs(u);
        }
        vs.emplace_back(v);
    }

    void rdfs(int v, int k) {
        used[v] = 1;
        blg[v] = k;
        C[k].emplace_back(v);
        for(int u:R[v]) {
            if(!used[u]) rdfs(u,k);
        }
    }

    int build() {
        int N = G.size();
        for(int v = 0; v < N; v++) {
            if(!used[v]) dfs(v);
        }

        fill(used.begin(),used.end(),0);
        int k = 0;
        for(int i = N-1; i >= 0; i--) {
            if(!used[vs[i]]) {
                T.emplace_back();
                C.emplace_back();
                rdfs(vs[i], k++);
            }
        }

        for(int v = 0; v < N; v++) {
            for(int u:G[v]) {
                if(blg[v] != blg[u]) T[blg[v]].emplace_back(blg[u]);
            }
        }

        for(int i = 0; i < k; i++) {
            sort(T[i].begin(),T[i].end());
            T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end());
        }
        return k;
    }

    int operator[](int k) const{return blg[k];}
};

template<typename T>
struct RangeEdge {
    vector<vector<edge<T>>> G;
    int N,sz,to,from;

    RangeEdge() {}
    RangeEdge(int N) : N(N) {
        sz = 1;
        while (sz < N) sz <<= 1;
        to = N;
        from = N+sz*2;
        G.resize(N+sz*4);
        for (int i = 0; i < N; ++i) {
            G[to+i+sz].emplace_back(i,0);
            G[i].emplace_back(from+i+sz,0);
        }
        for (int i = 1; i < sz; ++i) {
            G[to+i].emplace_back(to+(i<<1|0),0);
            G[to+i].emplace_back(to+(i<<1|1),0);
            G[from+(i<<1|0)].emplace_back(from+i,0);
            G[from+(i<<1|1)].emplace_back(from+i,0);
        }
    }

private:

    void update(int l, int r, int v, int flag) {
        l += sz; r += sz;
        while (l < r) {
            if (l & 1) {
                if (flag) G[v].emplace_back(to+l,0);
                else G[from+l].emplace_back(v,0);
                ++l;
            }
            l >>= 1;
            if (r & 1) {
                --r;
                if (flag) G[v].emplace_back(to+r,0);
                else G[from+r].emplace_back(v,0);
            }
            r >>= 1; 
        }
    }

public:

    void addedge(int fromL, int fromR, int toL, int toR, T cost) {
        if (fromL >= fromR or toL >= toR) return;
        int M = G.size();
        G.emplace_back();
        G.emplace_back();
        G[M].emplace_back(M+1,cost);
        update(fromL,fromR,M,0);
        update(toL,toR,M+1,1);
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<int> x(N),y(N);
    rep(i,N) cin >> x[i] >> y[i];

    vector<int> idx(N),idy(N);
    iota(all(idx),0); iota(all(idy),0);
    sort(all(idx),[&](int i, int j){return x[i] < x[j];});
    sort(all(idy),[&](int i, int j){return y[i] < y[j];});
    sort(all(x)); sort(all(y));
    vector<int> invx(N),invy(N);
    rep(i,N) {
        invx[idx[i]] = i;
        invy[idy[i]] = i;
    }

    auto check=[&](int mid) {
        RangeEdge<int> RE(2*N);
        rep(i,N) {
            //x[i],x[j]
            int l = upper_bound(all(x),x[i]-mid) - x.begin();
            int r = lower_bound(all(x),x[i]+mid) - x.begin();
            RE.addedge(l,i,N+invy[idx[i]],N+invy[idx[i]]+1,1);
            RE.addedge(i+1,r,N+invy[idx[i]],N+invy[idx[i]]+1,1);

            //x[i],y[j]
            l = upper_bound(all(y),x[i]-mid) - y.begin();
            r = lower_bound(all(y),x[i]+mid) - y.begin();
            RE.addedge(N+l,N+r,N+invy[idx[i]],N+invy[idx[i]]+1,1);

            //y[i],x[j]
            r = lower_bound(all(x),y[i]+mid) - x.begin();
            l = upper_bound(all(x),y[i]-mid) - x.begin();
            RE.addedge(l,r,invx[idy[i]],invx[idy[i]]+1,1);

            //y[i],y[j]
            l = upper_bound(all(y),y[i]-mid) - y.begin();
            r = lower_bound(all(y),y[i]+mid) - y.begin();
            RE.addedge(N+l,N+i,invx[idy[i]],invx[idy[i]]+1,1);
            RE.addedge(N+i+1,N+r,invx[idy[i]],invx[idy[i]]+1,1);
        }
        
        int M = RE.G.size();
        StronglyConnectedComponent scc(M);
        rep(i,M) {
            for (auto &e : RE.G[i]) {
                scc.add_edge(i,e.to);
            }
        }
        scc.build();

        rep(i,N) {
            int u = invx[i];
            int v = invy[i]+N;
            if (scc[u]==scc[v]) return false;
        }
        return true;
    };
    
    int ok = 0;
    int ng = 1e9;
    while (abs(ok-ng)>1) {
        int mid = (ok+ng)/2;
        if (check(mid)) ok = mid;
        else ng = mid;
    }

    cout << ok << ln;
}


Measured memory_bytes: 95868