题目描述

给你一个 $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$（以上5个数都要异或上一次询问的答案 $last$，$last$ 初始为 $0$ ），表示一组询问，要求找到以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩形中的第 $k$ 小数。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1
3

说明/提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$1 \leq q \leq 4 \times 10^4$，$0 \leq a_{i, j} \leq 10^9$。