rt：

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=5e2+10,maxm=25e4+10,mod=1e9+7;

int n,ln,q,a[maxn][maxn],ls[maxm],t[maxn][maxn],ans[maxm];
struct node{int x1,y1,x2,y2,k,id,l,r;}tmp;
queue<node> qt,in;
pair<int,pii> sd[maxm];
int sum(int x1,int y1,int x2,int y2){
	int ans=0;
	#define tk(x,y,k) for(int i=x;i;i-=i&-i) for(int j=y;j;j-=j&-j) ans+=t[i][j]*k
	tk(x2,y2,1);tk(x1,y2,-1);tk(x1,y1,1);tk(x2,y1,-1);
	#undef tk
	return ans;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	rep(i,1,n) rep(j,1,n) cin>>a[i][j],ls[++ln]=a[i][j];
	sort(ls+1,ls+ln+1),ln=unique(ls+1,ls+ln+1)-ls-1;
	rep(i,1,n) rep(j,1,n) a[i][j]=lower_bound(ls+1,ls+ln+1,a[i][j])-ls,sd[(i-1)*n+j]={a[i][j],{i,j}};
	rep(i,1,q) cin>>tmp.x1>>tmp.y1>>tmp.x2>>tmp.y2>>tmp.k,tmp.l=1,tmp.r=1e6,tmp.id=i,qt.push(tmp);
	for(sort(sd+1,sd+n*n+1);qt.size();memset(t,0,sizeof t)){
		for(int now=1,mid;1;qt.pop()){
			for(;qt.size();qt.pop()){
				tmp=qt.front(),mid=tmp.l+tmp.r>>1;
				if(tmp.l<=tmp.r) break;
			}
//			cout<<tmp.l<<" "<<tmp.r<<"]\n";
			if(sd[now].fi>mid||now>n*n||qt.empty()) break;
			for(;sd[now].fi<mid&&now<=n*n;++now)
				for(int x=sd[now].se.fi;x<=n;x+=x&-x) for(int y=sd[now].se.se;y<=n;y+=y&-y) ++t[x][y];
			int rk=sum(tmp.x1-1,tmp.y1-1,tmp.x2,tmp.y2)+1;
//			cout<<tmp.l<<" "<<tmp.r<<":"<<tmp.id<<' '<<now<<' '<<mid<<':'<<tmp.k<<","<<rk<<"]\n";
			if(rk<=tmp.k) tmp.l=mid+1,ans[tmp.id]=mid,in.push(tmp);
			else tmp.r=mid-1,qt.push(tmp);
		}
		for(;in.size();in.pop()) qt.push(in.front());
	}
	rep(i,1,q) cout<<ls[ans[i]]<<'\n';
	return 0;
}/*
3 4
0 1000000000 0
1000000000 0 1000000000
0 1000000000 0
1 1 3 3 5
1 1 3 3 6
1 1 2 2 2
1 1 2 2 3

*/