#include<bits/stdc++.h>
#define AC return 0;
#define pr(n) printf("%d",(n))
#define hh puts("")
#define kg printf(" ")
using namespace std;
namespace fr{
	int read()
	{
		int x=0,flag=1;
		char ch=getchar();
		for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')flag=-1;
		for(;ch<='9'&&ch>='0';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
		return flag*x;
	}
}
using namespace fr;
const int N = 1e3+3,M=1e6+6;
struct node{
	int x,y,x1,y1,k,id;
}a[M],a1[M],a2[M];
int c[N][N],n,m;
int ans[M];
int lb(int x){return x&-x;}
void add(int x,int y,int w)
{
	for(int i=x;i<=n;i+=lb(i))
		for(int j=y;j<=n;j+=lb(j))
			c[i][j]+=w;
		
}
int ask(int x,int y)
{
	int res=0;
	for(;x;x-=lb(x))
	for(;y;y-=lb(y))
		res+=c[x][y];
	return res;
}
void solve(int L,int R,int l,int r)
{
	if(l>r)return ;
	if(L==R)
	{
		for(int i=l;i<=r;i++)
			ans[a[i].id]=L;
		return ;
	}
	int mid=(L+R)>>1;
	int l1=0,l2=0;
	
	for(int i=l;i<=r;i++)
	{
		if(!a[i].id)
		{
			if(a[i].k<=mid)
				add(a[i].x,a[i].y,1),a1[++l1]=a[i];
			else a2[++l2]=a[i];
		}
		else
		{
			int now=ask(a[i].x1,a[i].y1)-ask(a[i].x-1,a[i].y1)-ask(a[i].x1,a[i].y-1)+ask(a[i].x-1,a[i].y-1);
			if(now>=a[i].k)
			{
				a1[++l1]=a[i];
			}
			else
			{
				a[i].k-=now;
				a2[++l2]=a[i];
			}
		}
	}
	for(int i=1;i<=l1;i++)a[l+i-1]=a1[i];
	for(int i=1;i<=l2;i++)a[l+l1+i-1]=a2[i];
	for(int i=l;i<=l+l1-1;++i)
	{
		if(!a[i].id&&a[i].k<=mid)
			add(a[i].x,a[i].y,-1);
	}
	solve(L,mid,l,l+l1-1);
	solve(mid+1,R,l+l1,r);
}
int tot;
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[++tot].k=read();
			a[tot].x=i,a[tot].y=j;
			a[tot].x1=a[tot].y1=a[tot].id=0;
		}
	}
	for(int i=1;i<=m;i++)
	{
		a[++tot].x=read();
		a[tot].y=read();
		a[tot].x1=read();
		a[tot].y1=read();
		a[tot].k=read();
		a[tot].id=i;
	}
	
	solve(INT_MIN,INT_MAX,1,tot);//这里变成±1e9会wa，这样会T
	for(int i=1;i<=m;i++)
	{
		pr(ans[i]);hh;
	}
	AC
}

wa/tle 0pts