#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e3 + 10;

struct pos {
	int x, y, v;
};

struct query {
	int x1, y1, x2, y2, k, id;
}; 

int n, m, q;
pos a[maxn * maxn];
query w[maxn * maxn];
int ans[maxn * maxn];
int b[maxn][maxn];
query q1[maxn * maxn], q2[maxn * maxn];
int cnt1, cnt2;

void add(int x, int y, int k) {
	for (int i = x; i <= n; i += i & i) {
		for (int j = y; j <= n; j += j & -j) {
			b[i][j] += k;
		}
	}
}

int query(int x, int y) {
	int r = 0;
	for (int i = x; i; i -= i & i) {
		for (int j = y; j; j -= j & -j) {
			r += b[i][j];
		}
	}
	return r;
}

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 solve(int l, int r, int ql, int qr) {
//	cout << l << " " << r << " " << ql << " " << qr << endl;
	if (ql > qr) return;
	if (l == r) {
		for (int i = ql; i <= qr; i++) ans[w[i].id] = a[l].v;
		return;
	}
	int mid = l + r >> 1;
	for (int i = l; i <= mid; i++) add(a[i].x, a[i].y, 1);
	cnt1 = cnt2 = 0;
	for (int i = ql; i <= qr; i++) {
		int s = query(w[i].x1, w[i].y1, w[i].x2, w[i].y2);
		if (s >= w[i].k) q1[++cnt1] = w[i];
		else w[i].k -= s, q2[++cnt2] = w[i];
	}
	for (int i = ql; i <= ql + cnt1 - 1; i++) w[i] = q1[i - ql + 1];
	for (int i = ql + cnt1; i <= qr; i++) w[i] = q2[i - ql - cnt1 + 1];
	for (int i = l; i <= mid; i++) add(a[i].x, a[i].y, -1);
	solve(l, mid, ql, ql + cnt1 - 1);
	solve(mid + 1, r, ql + cnt1, qr);
}

signed main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int x;
			cin >> x;
			a[++m] = {i, j, x};
		}
	}
	sort(a + 1, a + 1 + m, [] (pos u, pos v) {
		return u.v < v.v;
	});
	for (int i = 1; i <= q; i++) {
		cin >> w[i].x1 >> w[i].y1 >> w[i].x2 >> w[i].y2 >> w[i].k;
		w[i].id = i;
	}
	solve(1, m, 1, q);
	for (int i = 1; i <= q; i++) cout << ans[i] << endl;
	return 0;
}