题目描述
给你一个 n×n 的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第 k 小数。
输入格式
第一行有两个整数,分别表示矩阵大小 n 和询问组数 q。
第 2 到第 (n+1) 行,每行 n 个整数,表示这个矩阵。第 (i+1) 行的第 j 个数表示矩阵第 i 行第 j 列的数 ai,j。
接下来 q 行,每行五个整数 x1,y1,x2,y2,k,表示一组询问,要求找到以 (x1,y1) 为左上角,(x2,y2) 为右下角的子矩形中的第 k 小数。
输出格式
对于每组询问,输出一行一个整数表示答案。
2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3
1
3
提示
数据规模与约定
- 对于 20% 的数据,保证 n≤100,q≤103。
- 对于 40% 的数据,保证 n≤300,q≤104。
- 对于 60% 的数据,保证 n≤400,q≤3×104。
- 对于 100% 的数据,保证 1≤n≤500,1≤q≤6×104,0≤ai,j≤109。