#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,tot,maxnum,dx,hes,num;
int dfn[10000001],low[10000001],ins[10000001],st[10000001];
int ans[10000001],he[10000001];
struct data {
	int nx,num;
}ed[10000001];
struct point {
	int x,y,loc;
}a[10000001],b[10000001],c[10000001];
void add(int u,int v) {
	ed[++tot].nx=he[u];
	ed[tot].num=v;
	he[u]=tot;
}
bool cmpx(point p,point q) {
	return p.x<q.x;
}
bool cmpy(point p,point q) {
	return p.y<q.y;
}
struct seg {
	struct da {
		int l,r,num;
	}t[10000001];
	void build(int i,int l,int r,bool jud) {
		if (jud==0) maxnum=max(maxnum,n+i);
			else maxnum=max(maxnum,n*5+i);
		t[i].l=l;
		t[i].r=r;
		if (l==r) {
			if (jud==0) {
				add(b[l].loc*2-1,(n+i)*2-1);
				add((n+i)*2,b[l].loc*2);
			}
			else {
				add(c[l].loc*2,(n*5+i)*2-1);
				add((n*5+i)*2,c[l].loc*2-1);
			}
			return;
		}
		int mid=(l+r)/2;
		build(i*2,l,mid,jud);
		build(i*2+1,mid+1,r,jud);
		if (!jud) {
			add((n+i*2)*2-1,(n+i)*2-1);
			add((n+i)*2,(n+i*2)*2);
			add((n+i*2+1)*2-1,(n+i)*2-1);
			add((n+i)*2,(n+i*2+1)*2);
		}
		else {
			add((n*5+i*2)*2-1,(n*5+i)*2-1);
			add((n*5+i)*2,(n*5+i*2)*2);
			add((n*5+i*2+1)*2-1,(n*5+i)*2-1);
			add((n*5+i)*2,(n*5+i*2+1)*2);
		}
	}
	void Add(int i,int x,int l,int r,bool jud) {
		int nowl=t[i].l,nowr=t[i].r;
		if (nowr<l||nowl>r) return;
		if (nowl>=l&&nowr<=r) {
			if (!jud) {
				add(x,(n+i)*2);
				add((n+i)*2-1,((x-1)^1)+1);
			}
			else {
				add(x,(n*5+i)*2);
				add((n*5+i)*2-1,((x-1)^1)+1);
			}
			return;
		}
		Add(i*2,x,l,r,jud);
		Add(i*2+1,x,l,r,jud);
	}
}t1,t2;
void Tarjan(int x) {
	dfn[x]=low[x]=++dx;
	st[++hes]=x;
	ins[x]=1;
	for (int i=he[x];i!=-1;i=ed[i].nx) {
		int kx=ed[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;
	num++;
	while (st[hes]!=x) {
		ans[st[hes]]=num;
		ins[st[hes]]=0;
		hes--;
	}
	ins[x]=0;
	ans[x]=num;
	hes--;
}
int findlx(int x) {
	int l=1,r=n+1;
	while (l<r) {
		int mid=(l+r)/2;
		if (b[mid].x<x) l=mid+1;
			else r=mid;
	}
	return l;
}
int findrx(int x) {
	int l=0,r=n;
	while (l<r) {
		int mid=(l+r+1)/2;
		if (b[mid].x>x) r=mid-1;
			else l=mid;
	}
	return l;
}
int findly(int x) {
	int l=1,r=n+1;
	while (l<r) {
		int mid=(l+r)/2;
		if (c[mid].y<x) l=mid+1;
			else r=mid;
	}
	return l;
}
int findry(int x) {
	int l=0,r=n;
	while (l<r) {
		int mid=(l+r+1)/2;
		if (c[mid].y>x) r=mid-1;
			else l=mid;
	}
	return l;
}
void build_graph(int x) {
	for (int i=1;i<=n;i++) {
		int kl=findlx(b[i].x-x+1),kr=i-1;
		if (kl<=kr) t1.Add(1,b[i].loc*2-1,kl,kr,0);
		kr=findrx(b[i].x+x-1);
		kl=i+1;
		if (kl<=kr) t1.Add(1,b[i].loc*2-1,kl,kr,0);
		kl=findly(b[i].x-x+1);
		kr=findry(b[i].x+x-1);
		if (kl<=kr) t2.Add(1,b[i].loc*2-1,kl,kr,1);
	}
	for (int i=1;i<=n;i++) {
		int kl=findly(c[i].y-x+1),kr=i-1;
		if (kl<=kr) t2.Add(1,c[i].loc*2,kl,kr,1);
		kr=findry(c[i].y+x-1);
		kl=i+1;
		if (kl<=kr) t2.Add(1,c[i].loc*2,kl,kr,1);
		kl=findlx(c[i].y-x+1);
		kr=findrx(c[i].y+x-1);
		if (kl<=kr) t1.Add(1,c[i].loc*2,kl,kr,0);
	}
}
bool check(int x) {
	maxnum=0;
	memset(he,-1,sizeof(he));
	tot=0;
	num=0;
	t1.build(1,1,n,0);
	t2.build(1,1,n,1);
	build_graph(x);
	memset(dfn,0,sizeof(dfn));
	memset(ins,0,sizeof(ins));
	dx=hes=num=0;
	for (int i=1;i<=maxnum*2;i++) if (!dfn[i]) Tarjan(i);
	for (int i=1;i<=maxnum;i++) if (ans[2*i-1]==ans[2*i]) return 0;
	return 1;
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d%d",&a[i].x,&a[i].y);
		a[i].loc=i;
	}
	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];
	int l=0,r=1e9;
	while (l<r) {
		int mid=(l+r+1)/2;
		if (check(mid)) l=mid;
			else r=mid-1;
	}
	printf("%d\n",l);
	return 0;
}

Measured memory_bytes: 150400