#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 505
#define Q 320005
using namespace std;
int n, m;
int tr[N][N];
int ans[Q];
struct Node{
int op;
int r, c, x;
int r1, c1, r2, c2, k;
int id;
}q[Q], lq[Q], rq[Q];
int lowbit(int x){
return x & -x;
}
void updata(int x,int y,int v){
for(int i = x;i <= n;i += lowbit(i))
for(int j = y;j <= n;j += lowbit(j))
tr[i][j] += v;
}
int query(int x,int y){
int ans = 0;
for(int i = x;i;i -= lowbit(i))
for(int j = y;j;j -= lowbit(j)){
ans += tr[i][j];
}
return ans;
}
void solve(int lv,int rv,int ql,int qr){
if(lv > rv || ql > qr) return ;
cerr << "solve: " << lv << " " << rv << " " << ql << " " << qr << endl;
if(lv == rv){
for(int i = ql;i <= qr;i ++ )
if(q[i].op == 2){
ans[q[i].id] = rv;
}
return ;
}
int mid = lv + rv >> 1;
int nl = 0, nr = 0;
for(int i = ql;i <= qr;i ++ ){
if(q[i].op == 1){ // insert
if(q[i].x <= mid) updata(q[i].r, q[i].c, 1), lq[ ++ nl] = q[i];
else rq[ ++ nr] = q[i];
}
else if(q[i].op == 2){ // query
int x1 = q[i].r1, y1 = q[i].c1, x2 = q[i].r2, y2 = q[i].c2;
int t = query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1);
// int t = query(q[i].r2, q[i].c2) - query(q[i].r2, q[i].c1-1) - query(q[i].r1-1, q[i].c2) + query(q[i].r1-1, q[i].c1-1);
if(t >= q[i].k) lq[ ++ nl] = q[i];
else{
q[i].k -= t;
rq[ ++ nr] = q[i];
}
}
}
for(int i = ql;i <= qr;i ++ )
if(q[i].op == 1)
if(q[i].x <= mid)
updata(q[i].r, q[i].c, -1);
for(int i = 1;i <= nl;i ++ ) q[ql + i - 1] = lq[i];
for(int i = 1;i <= nr;i ++ ) q[ql + nl + i - 1] = rq[i];
solve(lv, mid, ql, ql + nl - 1);
solve(mid + 1, rv, ql + nl, qr);
}
int main(){
scanf("%d%d", &n, &m);
int t = 0;
for(int i = 1;i <= n;i ++ )
for(int j = 1;j <= n;j ++ ){
scanf("%d", &q[ ++ t].x);
q[t].id = t;
q[t].r = i, q[t].c = j;
q[t].op = 1;
}
for(int i = 1;i <= m;i ++ ){
q[ ++ t].op = 2;
q[t].id = t;
scanf("%d%d%d%d%d", &q[t].r1, &q[t].c1, &q[t].r2, &q[t].c2, &q[t].k);
}
solve(0, 1e9, 1, t);
for(int i = 1;i <= m;i ++ )
printf("%d\n", ans[n * n + i]);
return 0;
}