#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

const char iname[]="matrice2.in";
const char oname[]="matrice2.out";
const int maxn=300*305;

ifstream f(iname);
ofstream g(oname);

int n,A[maxn],h[maxn],in[maxn],Q[maxn][2],j,i,step,q,a[maxn],poz[maxn],pozq[maxn],x,y;
vector<int> E[maxn];

inline int anc(int x)
{
    int y,aux;
    for(y=x;y!=A[y];y=A[y]);
    for(;x!=A[x];x=aux)
        aux=A[x],A[x]=y;
    return y;
}

inline void merge(int x,int y)
{
    if(h[x]>h[y])
        A[y]=x;
    else
        A[x]=y;
    if(h[x]==h[y])
        ++h[y];
}

inline bool fcomp(const int &x,const int &y)
{
    return a[x]<a[y];
}

inline bool fcompq(const int &x,const int &y)
{
    return in[x]<in[y];
}

int main()
{
    f>>n>>q;
    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
        {
            f>>a[i*n+j],poz[i*n+j]=i*n+j;
            if(i>0)
                E[i*n+j].push_back(i*n-n+j),E[i*n+j-n].push_back(i*n+j);
            if(j>0)
                E[i*n+j-1].push_back(i*n+j),E[i*n+j].push_back(i*n+j-1);
        }
    for(i=1;i<=q;++i)
        f>>x>>y,Q[i][0]=(x-1)*n+y-1,f>>x>>y,Q[i][1]=(x-1)*n+y-1;
    n*=n;
    sort(poz,poz+n,fcomp);
    for(step=1;step<a[poz[n-1]]+1;step<<=1);
    for(i=1;i<=q;++i)
        in[i]=a[poz[n-1]]+1;
    for(;step;step>>=1)
    {
        for(i=1;i<=q;++i)
            in[i]-=step,pozq[i]=i;
        sort(pozq+1,pozq+q+1,fcompq);
        for(i=0;i<n;++i)
            A[i]=i,h[i]=1;
        j=q;
        for(i=n-1;i>=0;--i)
        {
            while(j&&in[pozq[j]]>a[poz[i]])
                if(anc(Q[pozq[j]][0])==anc(Q[pozq[j]][1]))
                    in[pozq[j]]+=step,--j;
                else
                    --j;
            for(vector<int>::iterator it=E[poz[i]].begin();it!=E[poz[i]].end();++it)
                if(a[*it]>=a[poz[i]]&&anc(poz[i])!=anc(*it))
                    merge(anc(poz[i]),anc(*it));
        }
        while(j)
            if(anc(Q[pozq[j]][0])==anc(Q[pozq[j]][1]))
                in[pozq[j]]+=step,--j;
            else
                --j;
    }
    for(i=1;i<=q;++i)
        g<<in[i]-1<<"\n";
}