Juanzhang

#include <bits/stdc++.h>
using namespace std;

#prag\
ma GCC optimize(3)
#define nc getchar()
const int maxn = 505, maxm = 6e4 + 10;
int Q[maxm], Q1[maxm], Q2[maxm], ans[maxm];
int n, m, len, c[maxn][maxn], data[maxn * maxn];

struct matrix {
  int x, y, k;

  inline bool operator < (const matrix &o) const {
    return k < o.k;
  }
} val[maxn * maxn];

struct node {
  int x1, y1, x2, y2, k, tid;
} a[maxm];

inline int read() {
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = x * 10 + (c ^ 48), c = nc;
  return x;
}


inline void add(int x, int y, int v) {
  for (register int i = x; i <= n; i += i & -i) {
    for (register int j = y; j <= n; j += j & -j) {
      c[i][j] += v;
    }
  }
}

inline int query(int x, int y) {
  register int res = 0;
  for (register int i = x; i; i &= i - 1) {
    for (register int j = y; j; j &= j - 1) {
      res += c[i][j];
    }
  }
  return res;
}

inline int query(int x1, int y1, int x2, int y2) {
  return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}

void divide(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (register int i = l; i <= r; ++i) {
      ans[a[Q[i]].tid] = ql;
    }
    return;
  }
  int mid = (ql + qr) >> 1, p1 = 0, p2 = 0;
  const int st = lower_bound(data + 1, data + len + 1, ql) - data, ed = upper_bound(data + 1, data + len + 1, mid) - data - 1;
  for (register int i = st; i <= ed; ++i) {
    add(val[i].x, val[i].y, 1);
  }
  for (register int i = l; i <= r; ++i) {
    node &val = a[Q[i]];
    const int s = query(val.x1, val.y1, val.x2, val.y2);
    val.k > s ? val.k -= s, Q2[++p2] = Q[i] : Q1[++p1] = Q[i];
  }
  for (register int i = st; i <= ed; ++i) {
    add(val[i].x, val[i].y, -1);
  }
  for (register int *i = Q + l, *j = Q1 + 1, *t = Q + l + p1; i != t; ++i, ++j) {
    *i = *j;
  }
  for (register int *i = Q + l + p1, *j = Q2 + 1, *t = Q + r + 1; i != t; ++i, ++j) {
    *i = *j;
  }
  divide(l, l + p1 - 1, ql, mid);
  divide(l + p1, r, mid + 1, qr);
}

int main() {
  n = read(), m = read();
  for (register int i = 1; i <= n; ++i) {
    for (register int j = 1; j <= n; ++j) {
      const int id = (i - 1) * n + j;
      val[id].k = read();
      val[id].x = i, val[id].y = j;
    }
  }
  len = n * n;
  sort(val + 1, val + len + 1);
  for (register int i = 1; i <= len; ++i) {
    data[i] = val[i].k;
  }
  for (register int i = 1; i <= m; ++i) {
    a[i].x1 = read(), a[i].y1 = read();
    a[i].x2 = read(), a[i].y2 = read();
    a[i].tid = Q[i] = i, a[i].k = read();
  }
  divide(1, m, 0, 1e9);
  for (register int i = 1; i <= m; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}