TLE，只有60pts

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=250005;
int n,q,a[N][N],xa[M],zs,cd,fk[M],b,c,d,e,k,cnt[M],js[M],ans[60005],lsh[M];
namespace io
{
	const int __SIZE = (1 << 21) + 1;
	char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
	#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
	inline void gc (char &x) { x = Gc(); }
	inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
	inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
		for(; __c > 31 && __c < 127 && __c != ' ' && __c != '\n' && __c != '\r'; ++s, __c = Gc()) *s = __c; *s = 0; }
	template <class I> inline bool gi (I &x) { _eof = 0;
		for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
		for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
	template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
struct XW
{
	int l1,r1,l2,r2,k,id;
}xw[M];
bool cmp(XW x,XW y)
{
	if(fk[x.l1]==fk[y.l1])
	{
		if(fk[x.r1]==fk[y.r1])
		{
			if(fk[x.l2]==fk[y.l2])
			{
				if(fk[x.l2]&1) return x.r2<y.r2;
				return x.r2>y.r2;
			}
			if(fk[x.r1]&1) return x.l2<y.l2;
			return x.l2>y.l2;
		}
		if(fk[x.l1]&1) return x.r1<y.r1;
		return x.r1>y.r1;
	}
	return x.l1<y.l1;
}
inline int ls(int x)
{
	return (x-1)*cd+1;
}
inline int rs(int x)
{
	return x*cd;
}
inline int Q(int ks)
{
	int zh=0;
	zh+=js[0];
	if(ks==1&&zh) return 0;
	for(int i=1;i<=fk[n*n];i++)
	{
		zh+=cnt[i];
		if(zh>=ks)
		{
			zh-=cnt[i];
			for(int j=ls(i);j<=rs(i);j++)
			{
				zh+=js[j];
				if(zh>=ks) return j;
			}
		}
	}
}
int main()
{
	gi(n);
	gi(q);
	cd=n/pow(q,0.25)/3+1;
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=n;++j)
		{
			int dq=(i-1)*n+j;
			gi(a[i][j]);
			xa[++zs]=a[i][j];
			fk[dq]=(dq-1)/cd+1;
		}
	}
	sort(xa+1,xa+zs+1);
	int len=unique(xa+1,xa+zs+1)-(xa+1);
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=n;++j)
		{
			int t=a[i][j];
			a[i][j]=lower_bound(xa+1,xa+len+1,a[i][j])-xa;
			lsh[a[i][j]]=t;
		}
	}
	for(register int i=1;i<=q;++i)
	{
		gi(xw[i].l1);
		gi(xw[i].r1);
		gi(xw[i].l2);
		gi(xw[i].r2);
		gi(xw[i].k);
		xw[i].id=i;
	}
	sort(xw+1,xw+q+1,cmp);
	int zuo=1,you=1,sha=1,xia=1;
	js[a[1][1]]=1;
	cnt[fk[a[1][1]]]=1;
	for(register int kk(1);kk<=q;++kk)
	{
		int l1=xw[kk].r1,l2=xw[kk].r2,r1=xw[kk].l1,r2=xw[kk].l2,xy=xw[kk].k;
		while(zuo>l1)
		{
			--zuo;
			for(int i=sha;i<=xia;++i)
			{
				++js[a[i][zuo]];
				++cnt[fk[a[i][zuo]]];
			}
		}
		while(you>l2)
		{
			for(int i=sha;i<=xia;++i)
			{
				--js[a[i][you]];
				--cnt[fk[a[i][you]]];
			}
			--you;
		}
		while(sha>r1)
		{
			sha--;
			for(int i=zuo;i<=you;++i)
			{
				++js[a[sha][i]];
				++cnt[fk[a[sha][i]]];
			}
		}
		while(xia>r2)
		{
			for(int i=zuo;i<=you;++i)
			{
				--js[a[xia][i]];
				--cnt[fk[a[xia][i]]];
			}
			--xia;
		}
		while(zuo<l1)
		{
			for(int i=sha;i<=xia;++i)
			{
				--js[a[i][zuo]];
				--cnt[fk[a[i][zuo]]];
			}
			++zuo;
		}
		while(you<l2)
		{
			++you;
			for(int i=sha;i<=xia;++i)
			{
				++js[a[i][you]];
				++cnt[fk[a[i][you]]];
			}
		}
		while(sha<r1)
		{
			for(int i=zuo;i<=you;++i)
			{
				--js[a[sha][i]];
				--cnt[fk[a[sha][i]]];
			}
			++sha;
		}
		while(xia<r2)
		{
			++xia;
			for(int i=zuo;i<=you;++i)
			{
				++js[a[xia][i]];
				++cnt[fk[a[xia][i]]];
			}
		}
		ans[xw[kk].id]=Q(xy);
	}
	for(register int i=1;i<=q;++i) printf("%d\n",lsh[ans[i]]);
	return 0;
}