#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+6;
const int M=1005;
const int inf=1e9+8;
struct node{int o,x,y,u,v,k,id;}q[N],q1[N],q2[N];
int n,m,cnt,tt;
int c[M][M],ans[N];
int lowbit(int x){return x&-x;}
void add(int x,int y,int d){
	for(int i=x;i<=n;i+=lowbit(i)){
		for(int j=y;j<=n;j+=lowbit(j)){
			c[i][j]+=d;
		}
	}
}
int query(int x,int y){
	int res=0;
	for(int i=x;i;i-=lowbit(i)){
		for(int j=y;j;j-=lowbit(j)){
			res+=c[i][j];
		}
	}
	return res;
}
void solve(int ql,int qr,int l,int r){
	if(ql>qr)return;
	//cout<<ql<<" "<<qr<<" "<<l<<" "<<r<<endl;
	if(l==r){
		for(int i=ql;i<=qr;i++){
			if(q[i].o==2)ans[q[i].id]=l;
		}
		return;
	}
	int mid=(l+r)>>1,p1=0,p2=0;
	for(int i=ql;i<=qr;i++){
		if(q[i].o==1){
			if(q[i].k<=mid){
				add(q[i].x,q[i].y,1);
				q1[++p1]=q[i];
			}
			else q2[++p2]=q[i];
		}
		else{
			int res=query(q[i].u,q[i].v)-query(q[i].x-1,q[i].v)-query(q[i].u,q[i].y-1)+query(q[i].x-1,q[i].y-1);
			if(res>=q[i].k)q1[++p1]=q[i];
			else{
				q[i].k-=res;
				q2[++p2]=q[i];
			}
		}
	}
	for(int i=1;i<=p1;i++){
		q[i+ql-1]=q1[i];
		if(q[i].o==1)add(q[i].x,q[i].y,-1);
	}
	for(int i=1;i<=p2;i++){
		q[i+ql+p1-1]=q2[i];
	}
	solve(ql,ql+p1-1,l,mid);
	solve(ql+p1,qr,mid+1,r);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int x;
			cin>>x;
			q[++tt]=(node){1,i,j,0,0,x,0};
		}
	}
	for(int i=1;i<=m;i++){
		int x,y,u,v,k;
		cin>>x>>y>>u>>v>>k;
		q[++tt]=(node){2,x,y,u,v,k,i};
	}
	solve(1,tt,-inf,inf);
	for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
	return 0;
}