#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,k,x1,x2,y1,y2,q,ls,rs,mid,s[505][505],ans=2e9,r;
vector<int> tree[505][505];
pair<int,pair<int,int> > pr[250005];
int a[505][505];
void add(int x,int y,int v){
	while(x<=n){
		int yx=y;
		while(yx<=n){
			tree[x][yx].push_back(v);
			yx+=yx&-yx;
		}
		x+=x&-x;
	}
}
int query(int x,int y,int v){
	int ans=0;
	if(v>s[x][y]){
		return x*y;
	}
	while(x){
		int yx=y;
		while(yx){
			ans+=lower_bound(tree[x][yx].begin(),tree[x][yx].end(),v)-tree[x][yx].begin();
			yx-=yx&-yx;
		}
		x-=x&-x;
	}
	return ans;
}
inline int read(){
    int x(0);
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
inline void write(int x){
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
int main(){
	n=read();q=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=read();
			pr[++r]={a[i][j],{i,j}};
		}
	}
	sort(pr+1,pr+r+1);
	for(int i=1;i<=r;i++){
		add(pr[i].second.first,pr[i].second.second,i);
		s[pr[i].second.first][pr[i].second.second]=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			s[i][j]=max(s[i-1][j],max(s[i][j-1],s[i][j]));
		}
	}
	while(q--){
		x1=read();y1=read();x2=read();y2=read();k=read();
		int tt,len=(x2-x1+1)*(y2-y1+1);
		ls=k,rs=s[x2][y2]-(len-k-1);
		while(ls<rs){
			mid=(ls+rs+1)>>1;
			tt=query(x2,y2,mid)+query(x1-1,y1-1,mid)-query(x2,y1-1,mid)-query(x1-1,y2,mid)+1;
			if(tt>k){
				rs=mid-1;
			}
			else{
				ls=mid;
			}
		}
		write(pr[ls].first);
		printf("\n");
	}
	return 0;
}

二维树状数组维护vector。

评测记录（大号）：

（n年前搞得远古东西