/*
裸地2-SAT问题 关键是模型转化
最小的最大 显然二分 关键是Judge的时候怎么判断
每个航班是早是晚直接影响判断
早晚只能选一个 如果我们定义bool变量xi表示 i航班是否早到
每个航班虚拟出两个点2*i 2*i+1 分别表示是否早到
然后就可以假设某个航班早到然后推导出一定连得某些边
然后就开始选点 尝试这个点选不选 看看最后是否合法
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 4400
using namespace std;
int n,l,r,g[maxn][],f[maxn],ans,c,s[maxn];
vector<int>G[maxn];
int Abs(int a)
{
return a<?-a:a;
}
void Add(int x,int y)
{
G[x^].push_back(y);G[y^].push_back(x);
}
bool Dfs(int x)
{
if(f[x^])return ;if(f[x])return ;
f[x]=;s[c++]=x;
for(int i=;i<G[x].size();i++)
if(!Dfs(G[x][i]))return ;
return ;
}
bool Solve()//选点
{
for(int i=;i<n*;i+=)
{
if(f[i]||f[i+])continue;c=;//表示同一航班的两个点只选一个
if(!Dfs(i))
{
while(c>)f[s[--c]]=;//撤销
if(!Dfs(i+))return ;
}
}
return ;
}
bool Judge(int x)
{
for(int i=;i<n*;i++)G[i].clear();
memset(f,,sizeof(f));
for(int i=;i<n;i++)for(int a=;a<;a++)
for(int j=i+;j<n;j++)for(int b=;b<;b++)
if(Abs(g[i][a]-g[j][b])<x)
//i*2+a 不能和 j*2+b 同时选 那就i*2+a连j*2+(b^1) j*2+b连i*2+(a^1)
Add(i*+(a^),j*+(b^));
return Solve();
}
int main()
{
while(scanf("%d",&n)==&&n)
{
l=r=ans=;
for(int i=;i<n;i++)
for(int j=;j<;j++)
{
scanf("%d",&g[i][j]);
r=max(r,g[i][j]);
}
while(l<=r)
{
int mid=(l+r)/;
if(Judge(mid))
{
ans=mid;l=mid+;
}
else r=mid-;
}
printf("%d\n",ans);
}
return ;
}