[国家集训队]矩阵乘法

题目背景

原 《补丁VS错误》请前往P2761

题目描述

给你一个N\*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数。

输入输出格式

输入格式


第一行两个数N,Q,表示矩阵大小和询问组数; 接下来N行N列一共N\*N个数,表示这个矩阵; 再接下来Q行每行5个数描述一个询问:x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。

输出格式


对于每组询问输出第K小的数。

输入输出样例

输入样例 #1

2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3

输出样例 #1

1
3

说明

矩阵中数字是10^9以内的非负整数; 20%的数据:N<=100,Q<=1000; 40%的数据:N<=300,Q<=10000; 60%的数据:N<=400,Q<=30000; 100%的数据:N<=500,Q<=60000。