Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

} 

int n,m;

#define MAXN 510

#define MAXQ 60010

int a[MAXN][MAXN];

int b[MAXN * MAXN],tot = 0;

int to[MAXN * MAXN],cnt = 0;

map<int,int> fr;

struct opt

{

	int r1,c1,r2,c2,k,type,id;

}q[MAXN * MAXN + MAXQ],q1[MAXN * MAXN + MAXQ],q2[MAXN * MAXN + MAXQ];

int cur = 0;

int ans[MAXQ];

int c[MAXN][MAXN];

inline int lowbit(int x){return x & (-x);}

#define rint register int

inline void add(int x,int y,int k)

{

	for(rint i = x;i <= n;i += lowbit(i))

		for(rint j = y;j <= n;j += lowbit(j))

			c[i][j] += k;

	return;

}

inline int query(int x,int y)

{

	rint res = 0;

	for(rint i = x;i >= 1;i -= lowbit(i))

		for(rint j = y;j >= 1;j -= lowbit(j))

			res += c[i][j];

	return res;

}

void solve(int l,int r,int L,int R)

{

	//cout << L << " " << R << endl;

	//for(int i = l;i <= r;++i)cout << q[i].r1 << " " << q[i].c1 << " " << q[i].r2 << " " << q[i].c2 << " " << q[i].k << " " << q[i].type << " " << q[i].id << endl;

	if(L == R)

	{

		for(rint i = l;i <= r;++i)

			if(q[i].type)ans[q[i].id] = L;

		return;

	}

	rint mid = ((L + R) >> 1);

	rint l1 = 0,l2 = 0;

	for(rint i = l;i <= r;++i)

	{

		if(q[i].type == 0)

		{

			if(fr[q[i].k] <= mid)add(q[i].r1,q[i].c1,1),q1[++l1] = q[i];

			else q2[++l2] = q[i];

		}

		else

		{

			register opt k = q[i];

			rint res = query(k.r2,k.c2) - query(k.r2,k.c1 - 1) - query(k.r1 - 1,k.c2) + query(k.r1 - 1,k.c1 - 1);

			if(res >= q[i].k)q1[++l1] = q[i];

			else q[i].k -= res,q2[++l2] = q[i];

		}

	}

	for(rint i = 1;i <= l1;++i)if(q1[i].type == 0)add(q1[i].r1,q1[i].c1,-1);

	for(rint i = 1;i <= l1;++i)q[l + i - 1] = q1[i];

	for(rint i = 1;i <= l2;++i)q[l + l1 - 1 + i] = q2[i];

	solve(l,l + l1 - 1,L,mid);solve(l + l1,r,mid + 1,R);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(rint i = 1;i <= n;++i)

		for(rint j = 1;j <= n;++j)

			a[i][j] = read();

	for(rint i = 1;i <= n;++i)

		for(rint j = 1;j <= n;++j)

			b[++tot] = a[i][j];

	sort(b + 1,b + 1 + tot);

	for(rint i = 1;i <= tot;++i)

	{

		if(i == 1 || b[i] != b[i - 1])

		{

			to[++cnt] = b[i];

			fr[b[i]] = cnt;

		}

	}

	for(rint i = 1;i <= n;++i)

	{

		for(rint j = 1;j <= n;++j)

		{

			++cur;

			q[cur].r1 = i;q[cur].c1 = j;

			q[cur].type = 0;q[cur].k = a[i][j];

		}

	}

	rint r1,c1,r2,c2;

	for(rint i = 1;i <= m;++i)

	{

		++cur;q[cur].id = i;q[cur].type = 1;

		q[cur].r1 = read();q[cur].c1 = read();q[cur].r2 = read();q[cur].c2 = read();

		q[cur].k = read();

	}

	solve(1,cur,1,cnt);

	for(rint i = 1;i <= m;++i)

	{

		printf("%d\n",to[ans[i]]);

	}

	return 0;

}