1
2
3
4
5

2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3

1
2

1
3

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

#include "ybwhead/ios.h"
using namespace std;
int n;
const int maxn = 5e2 + 10;
struct node
{
    int x, y, w;
} ma[maxn * maxn];
int cnt;
int cmp(node a, node b)
{
    return a.w < b.w;
}
struct query
{
    int x1, y1, x2, y2, w, id, ans;
} q[600000];
int tot;
struct BIT
{
    int n;
    int C[maxn][maxn];
    BIT(int N = 0)
    {
        n = N;
    }
    inline int lowbit(int x) { return x & (-x); }
    inline void add(int x, int y, int v)
    {
        for (register int i = x; i <= n; i += lowbit(i))
            for (register int j = y; j <= n; j += lowbit(j))
                C[i][j] += v;
    }
    inline int pre(int x, int y)
    {
        int ans = 0;
        for (register int i = x; i > 0; i -= lowbit(i))
            for (register int j = y; j > 0; j -= lowbit(j))
                ans += C[i][j];
        return ans;
    }
    inline int submat(int x1, int y1, int x2, int y2)
    {
        int ans = pre(x2, y2);
        ans -= pre(x1 - 1, y2) + pre(x2, y1 - 1);
        ans += pre(x1 - 1, y1 - 1);
        return ans;
    }
} xx;
int t1[maxn * 2000], t2[maxn * 2000];
void solve(int l, int r, int ll, int rr)
{
    if (ll > rr)
        return;
    if (l == r)
    {
        for (int i = ll; i <= rr; i++)
            q[q[i].id].ans = ma[l].w;
        return;
    }
    int mid = (l + r) >> 1;
    for (int i = l; i <= mid; i++)
        xx.add(ma[i].x, ma[i].y, 1);
    int cnt1, cnt2;
    cnt1 = cnt2 = 0;
    for (int i = ll; i <= rr; i++)
    {
        int u = q[i].id;
        int s = xx.submat(q[u].x1, q[u].y1, q[u].x2, q[u].y2);
        if (s >= q[u].w)
            t1[++cnt1] = u;
        else
            t2[++cnt2] = u;
    }
    for (int i = ll; i < ll + cnt1; i++)
        q[i].id = t1[i - ll + 1];
    for (int i = ll + cnt1; i <= rr; i++)
        q[i].id = t2[i - ll - cnt1 + 1];
    solve(mid + 1, r, ll + cnt1, rr);
    for (int i = l; i <= mid; i++)
        xx.add(ma[i].x, ma[i].y, -1);
    solve(l, mid, ll, ll + cnt1 - 1);
}
int main()
{
    int qq;
    yin >> n >> qq;
    xx.n = n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int x;
            yin >> x;
            ma[++cnt] = (node){i, j, x};
        }
    }
    sort(ma + 1, ma + cnt + 1, cmp);
    for (int i = 1; i <= qq; i++)
    {
        int x1, x2, y1, y2, k;
        yin >> x1 >> y1 >> x2 >> y2 >> k;
        q[++tot] = (query){x1, y1, x2, y2, k, i, 0};
    }
    solve(1, cnt, 1, tot);
    for (int i = 1; i <= tot; i++)
        yout << q[i].ans << endl;
    return 0;
}