记录编号	167615	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]矩阵乘法	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	10.059 s
提交时间	2015-06-27 00:04:59	内存使用	6.93 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
//#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <ctime>
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 502, maxq = 60004;

int S[maxn][maxn], N, Q, tmp[maxq];
struct Query{int id, a1, b1, a2, b2, ans, k;}q[maxq];
inline bool operator < (const Query &a, const Query &b){return a.id < b.id;}

struct val{int x, y, v;}v[maxn*maxn];
inline bool operator < (const val &a, const val &b){return a.v < b.v;}

inline void init(){
	getd(N), getd(Q);
	int i, j, t = 0;
	for(i = 1;i <= N;++i)for(j = 1;j <= N;++j){
		v[t].x = i, v[t].y = j;
		getd(v[t++].v);
	}
	sort(v, v + t);
	for(i = 0;i < Q;++i)
		q[i].id = i, getd(q[i].a1), getd(q[i].b1), getd(q[i].a2), getd(q[i].b2), getd(q[i].k);
}

#define Sum(a, b) (S[a][b])

inline int calc(const Query &q){
	int a1 = q.a1-1, b1 = q.b1-1, a2 = q.a2, b2 = q.b2;
	return Sum(a1, b1) - Sum(a1, b2) - Sum(a2, b1) + Sum(a2, b2);
}

inline bool In(val *it, const Query q){return it->x>=q.a1 && it->x<=q.a2 && it->y>=q.b1 && it->y<=q.b2;}

int tmpS[maxn][maxn];
inline void work(){
	int i, j, k, end = Q, tcnt;
	val *b = v, *it;
	for(i = 0;i < N;++i, b += N){
		for(it = b;it < b + N;++it)++tmpS[it->x][it->y];
		for(j = 1;j <= N;++j)for(k = 1;k <= N;++k)tmpS[j][k] -= tmpS[j-1][k-1] - tmpS[j-1][k] - tmpS[j][k-1];
		for(j = 1;j <= N;++j)for(k = 1;k <= N;++k)S[j][k] += tmpS[j][k], tmpS[j][k] = 0;
		for(tcnt = j = 0;j < end;++j)if(calc(q[j]) >= q[j].k){
			swap(q[j--], q[--end]);
			tmp[tcnt++] = end;
		}
		for(j = 0;j < tcnt;++j){
			Query &qr = q[tmp[j]];
			k = calc(qr) - qr.k;
			for(it = b + N - 1;it >= b;--it)if(In(it, qr)){
				if(--k < 0){
					qr.ans = it->v;
					break;
				}
			}
		}
	}
	sort(q, q + Q);
	for(i = 0;i < Q;++i)printf("%d\n", q[i].ans);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(nt2012_mat);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif

	init();
	work();

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}