#include <bits/stdc++.h>
#define x first
#define y second
#define N 90002
using namespace std;
ifstream in("matrice2.in");
ofstream out("matrice2.out");
pair<int,int> a[N],q[N],qq[N];
int s[N],g[N],d[4],n;
int gr(int i)
{
	if(g[i]==-1)
		return n*n+i;
	if(i!=g[i])
		g[i]=gr(g[i]);
	return g[i];
}
void ad(int i,int j)
{
	if(j<0||j>=n*n||g[j]==-1||abs(i%n-j%n)+abs(i/n-j/n)!=1)
		return;
	g[gr(j)]=gr(i);
}
int main()
{
	int m,i,j,k,l;
	in>>n>>m;
	for(i=0;i<n*n;i++)
		in>>a[i].x,a[i].y=i;
	sort(a,a+n*n);
	for(i=0;i<m;i++)
		in>>k>>q[i].x>>l>>q[i].y,q[i].x+=--k*n-1,q[i].y+=--l*n-1;
	d[0]=1;d[1]=n;d[2]=-1;d[3]=-n;
	for(k=1;k<=a[n*n-1].x;k*=2);
	while(k/=2)
	{
		for(i=0;i<m;i++)
			qq[i]={s[i]+k,i};
		sort(qq,qq+m);
		memset(g,-1,sizeof(g));
		for(i=n*n-1,j=m-1;i>=0;)
		{
			for(;j>=0&&a[i].x<qq[j].x;j--)
				if(gr(q[qq[j].y].x)==gr(q[qq[j].y].y))
					s[qq[j].y]+=k;
			do{
				g[a[i].y]=a[i].y;
				for(l=0;l<4;l++)
					ad(a[i].y,a[i].y+d[l]);
			}while(--i>=0&&a[i].x==a[i+1].x);
		}
		for(;j>=0;j--)
			if(gr(q[qq[j].y].x)==gr(q[qq[j].y].y))
				s[qq[j].y]+=k;
	}
	for(i=0;i<m;i++)
		out<<s[i]<<"\n";
	return 0;
}