#ox8kfm. 矩阵乘法

时间限制：1.5 s       空间限制：125 MiB       标签： 整体二分 数据结构 树状数组 二维树状数组 扫描线 离散化 莫队 二维莫队 

算法难度等级：6       思维难度等级：4       实现难度等级：5

题目描述

给你一个 $n \times n$ 的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第 $k$ 小数。

输入格式

第一行有两个整数，分别表示矩阵大小 $n$ 和询问组数 $q$。

第 $2$ 到第 $(n + 1)$ 行，每行 $n$ 个整数，表示这个矩阵。第 $(i + 1)$ 行的第 $j$ 个数表示矩阵第 $i$ 行第 $j$ 列的数 $a_{i, j}$。

接下来 $q$ 行，每行五个整数 $x_1, y_1, x_2, y_2, k$，表示一组询问，要求找到以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩形中的第 $k$ 小数。

输出格式

对于每组询问，输出一行一个整数表示答案。

样例输入输出

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

1
3

数据范围

• 对于 $20\%$ 的数据，保证 $n \leq 100$，$q \leq 10^3$。
• 对于 $40\%$ 的数据，保证 $n \leq 300$，$q \leq 10^4$。
• 对于 $60\%$ 的数据，保证 $n \leq 400$，$q \leq 3 \times 10^4$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 500$，$1 \leq q \leq 6 \times 10^4$，$0 \leq a_{i, j} \leq 10^9$。