[国家集训队] 矩阵乘法

题目描述

给你一个 $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$ 小数。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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$。