#include<bits/stdc++.h>
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
    int ret = 0,f = 0;char ch = getc();
    while (!isdigit (ch)) {
        if (ch == '-') f = 1;
        ch = getc();
    }
    while (isdigit (ch)) {
        ret = ret * 10 + ch - 48;
        ch = getc();
    }
    return f?-ret:ret;
}
const int B = 36;
int n, q;
int a[501][501];
vector<int>t[501][501], h[501][501];
bitset<B*B+1>bb[4];
int tt[4][B*B+1];
int lowbit(int x){
    return x & (-x);
}
int p[500];
int ord[250001];
int len;
int tong[250001];
bitset<250001>bit;
int kk[250001];
int k_[250001];
void pai(vector<int> &g){
    int len = g.size();
    for(int i = 1; i <= len; i++)kk[i] = g[i-1];
    memset(p, 0, sizeof(p));
    for(int i = 1; i <= len; ++i)p[kk[i]%500]++;
    for(int i = 1; i < 500; ++i)p[i] += p[i - 1];
    for(int i = len; i >= 1; i--)k_[p[kk[i]%500]--] = kk[i]; 
    memset(p, 0, sizeof(p));
    for(int i = 1; i <= len; ++i)p[k_[i]/500]++;
    for(int i = 1; i < 500; ++i)p[i] += p[i - 1];
    for(int i = len; i >= 1; i--)kk[p[k_[i]/500]--] = k_[i];
    for(int i = 0; i < len; i++)g[i] = kk[i+1];
}
int s[4][B*B+1];
int cnt[4];
void solve(int op, int x, int y){
    if(x%B==0||y%B==0)return;
    for(int i = x/B*B+1; i <= x; ++i){
        for(int j = y/B*B+1; j <= y; ++j){
            s[op][++cnt[op]] = a[i][j];
        }
    }
    memset(p, 0, sizeof(p));
    for(int i = 1; i <= cnt[op]; ++i)p[s[op][i]%500]++;
    for(int i = 1; i < 500; ++i)p[i] += p[i - 1];
    for(int i = cnt[op]; i >= 1; i--)k_[p[s[op][i]%500]--] = s[op][i]; 
    memset(p, 0, sizeof(p));
    for(int i = 1; i <= cnt[op]; ++i)p[k_[i]/500]++;
    for(int i = 1; i < 500; ++i)p[i] += p[i - 1];
    for(int i = cnt[op]; i >= 1; i--)s[op][p[k_[i]/500]--] = k_[i];
}
int mx;
int find(int op){
    int l = 1, r = cnt[op], ans = 0;
    while(l <= r){
        int mid = l+r>>1;
        if(s[op][mid] <= mx)ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}
int get_t(int x, int y){
    int len = t[x][y].size();
    if(!len)return 0;
    if(t[x][y][len - 1] <= mx)return len;
    int ans = upper_bound(t[x][y].begin(), t[x][y].end(), mx) - t[x][y].begin();
    return ans;
}
int get_h(int x, int y){
    int len = h[x][y].size();
    if(!len)return 0;
    if(h[x][y][len - 1] <= mx)return len;
    int ans = upper_bound(h[x][y].begin(), h[x][y].end(), mx) - h[x][y].begin();
    return ans;
}
int get(int x, int y){
    int ans = get_t(x/B*B, y/B*B);
    if(x % B != 0){
        int nowy = y / B;
        while(nowy){
            ans += get_h(x, nowy*B);
            nowy -= lowbit(nowy);
        }
    }
    if(y % B != 0){
        int nowx = x / B;
        while(nowx){
            ans += get_h(nowx*B, y);
            nowx -= lowbit(nowx);
        }
    }
    return ans;
}
int check(int x, int y, int x_, int y_, int mm){
    mx = mm;
    int ans = find(0) + find(1) - find(2) - find(3);
    ans += get(x_, y_);
    ans -= get(x_, y - 1);
    ans -= get(x - 1, y_);
    ans += get(x - 1, y - 1);
    return ans;
}
signed main(){
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            a[i][j]=read();
            ord[++len]=a[i][j];
        }
    }
    sort(ord+1,ord+1+len);
    int len_ = len;
    len = 0;
    for(int i = 1; i <= len_; ++i){
        if(i == 1 || ord[i] != ord[i - 1]){
            ord[++len] = ord[i];
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            a[i][j] = lower_bound(ord+1, ord+1+len, a[i][j])-ord;
        }
    }
    for(int i = B; i <= n; i += B){
        for(int j = B; j <= n; j += B){
            t[i][j].resize(i*j);
            int now=0;
            for(int x = 1; x <= i; ++x){
                for(int y = 1; y <= j; ++y){
                    tong[a[x][y]]++;
                    bit[a[x][y]] = 1;
                }
            }
            for(int k = bit._Find_first(); k != bit.size(); k = bit._Find_next(k)){
                while(tong[k]--){
                    t[i][j][now++] = k;
                }
                bit[k] = 0;
                tong[k]++;
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i % B == 0 && j % B != 0){
                int preij = i - lowbit(i/B)*B;
                h[i][j].resize((i-preij)*(j-j/B*B));
                int now=0;
                for(int x = preij + 1; x <= i; ++x){
                    for(int y = j / B * B + 1; y <= j; ++y){
                        h[i][j][now++] = a[x][y];
                    }
                }
                pai(h[i][j]);
            }
            if(i % B != 0 && j % B == 0){
                int preij = j - lowbit(j/B)*B;
                h[i][j].resize((j-preij)*(i-i/B*B));
                int now=0;
                for(int x = i / B * B + 1; x <= i; ++x){
                    for(int y = j - lowbit(j/B)*B + 1; y <= j; ++y){
                        h[i][j][now++] = a[x][y];
                    }
                }
                pai(h[i][j]);
            }
        }
    }
    while(q--){
        int x, y, x_, y_, k;
        x=read();
        y=read();
        x_=read();
        y_=read();
        k=read();
        cnt[0] = cnt[1] = cnt[2] = cnt[3] = 0;
        solve(0, x_, y_);
        solve(1, x - 1, y - 1);
        solve(2, x_, y - 1);
        solve(3, x - 1, y_);
        int l = 1, r = len, ans;
        while(l <= r){
            int mid = l+r>>1;
            if(check(x, y, x_, y_, mid) >= k){
                ans = mid;
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        printf("%d\n", ord[ans]);
    }
    return 0;
}

RT，还差0.1s