#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}


class range_tsort {
public:
    int n, sz, V;
	vector<vector<int> > G;
	vector<int> deg;
    void add_edge(const int from, const int to){
        G[from].push_back(to), ++deg[to];
    }
    vector<int> ord, low;
    stack<int> st;
    void dfs(const int u, int& tm){
        ord[u] = low[u] = tm++, st.push(u);
        for(int v : G[u]){
            if(ord[v] < 0){
                dfs(v, tm);
                low[u] = min(low[u], low[v]);
            }else if(cmp[v] < 0){
                low[u] = min(low[u], ord[v]);
            }
        }
        if(ord[u] == low[u]){
            while(true){
                const int v = st.top();
                st.pop();
                cmp[v] = cnt;
                if(v == u) break;
            }
            ++cnt;
        }
    }
    vector<int> cmp;
    int cnt;
	range_tsort(const int node_size) : n(node_size), sz(1){
        while(sz < n) sz *= 2;
		V = 3 * sz - 1;
		G.resize(V), deg.resize(V, 0);
        
        for(int i = 1; i < sz; ++i){
			add_edge(i, 2 * i), add_edge(i, 2 * i + 1);
			if(2 * i >= sz) add_edge(2 * i, V - i), add_edge(2 * i + 1, V - i);
			else add_edge(V - 2 * i, V - i), add_edge(V - 2 * i - 1, V - i);
		}
    }
    // [p, q) → [r, s)
    void add_edge(int p, int q, int r, int s){
		if(p >= q || r >= s) return;
        p += sz, q += sz, r += sz, s += sz;
		G.push_back({}), deg.push_back(0);
		while(p != q){
			if(p & 1) add_edge((p >= sz) ? (p++) : (V - p++), (int)G.size()  - 1);
			if(q & 1) add_edge((--q >= sz) ? (q) : (V - q), (int)G.size()  - 1);
			p >>= 1, q >>= 1;
		}
		while(r != s){
			if(r & 1) add_edge((int)G.size()  - 1, r++);
			if(s & 1) add_edge((int)G.size()  - 1, --s);
			r >>= 1, s >>= 1;
		}
    }
	int solve(){ // 強連結成分の数を返す
        V = G.size();
        ord.resize(V,-1);
        low.resize(V,0), cmp.resize(V, -1), cnt=0;
        
        int tm = 0;
        for(int i = 0; i < V; ++i){
            if(ord[i] < 0) dfs(i, tm);
        }
        for(int i = 0; i < V; ++i) cmp[i] = cnt - 1 - cmp[i];
        // rep(i,V){
        //     cerr << i << " " << cmp[i] << endl;
        // }
        
        return cnt;
    }
};

int main(){
    int n;
    cin >> n;
    vector<pair<int,int> > x,y;
    rep(i,n){
        int a;
        cin >> a;
        x.push_back(MP(a,i));
        cin >> a;
        y.push_back(MP(a,i));
    }
    sort(all(x));
    sort(all(y));
    vector<int>idx(n),idy(n);
    rep(i,n){
        idx[x[i].second] = i+n;
        idy[y[i].second] = i;
    }
    int ok = -1;
    int ng = 1000000000;
    while(ng-ok>1){
        int mid = (ok+ng)/2;
        range_tsort rt(2*n);
        rep(i,n){
            int K = x[i].first;
            int l,r,s;
            l = lower_bound(all(x),MP(K-mid,-10)) - x.begin();
            r = upper_bound(all(x),MP(K+mid,inf)) - x.begin();
            s = idy[x[i].second];
            rt.add_edge(s,s+1,l+n,i+n);
            rt.add_edge(s,s+1,i+1+n,r+n);

            l = lower_bound(all(y),MP(K-mid,-10)) - y.begin();
            r = upper_bound(all(y),MP(K+mid,inf)) - y.begin();
            rt.add_edge(s,s+1,l,r);
            
            K = y[i].first;
            s = idx[y[i].second];

            l = lower_bound(all(x),MP(K-mid,-10)) - x.begin();
            r = upper_bound(all(x),MP(K+mid,inf)) - x.begin();
            rt.add_edge(s,s+1,l+n,r+n);
            
            l = lower_bound(all(y),MP(K-mid,-10)) - y.begin();
            r = upper_bound(all(y),MP(K+mid,inf)) - y.begin();
            rt.add_edge(s,s+1,l,i);
            rt.add_edge(s,s+1,i+1,r);
        }
        rt.solve();
        // cerr << rt.solve() << endl;
        bool flag = 0;
        // rep(i,2*n){
        //     cerr << rt.cmp[rt.sz + i] << " ";
        // }
        // cerr << endl;
        rep(i,n){
            if(rt.cmp[rt.sz+idx[i]]==rt.cmp[rt.sz+idy[i]]){
                flag = 1;
                break;
            }
        }
        if(!flag){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    cout << ok+1 << endl;
    return 0;
}

Measured memory_bytes: 18216