题目描述

小灰灰拿到了一个 $n \times n$ 的方阵 $a$，其中第 $i$ 行第 $j$ 列的元素满足：

现在小蓝对该方阵进行了 $q$ 次操作，每次操作属于以下两种类型之一：

• 输入 1 x y len，表示将以 $(x, y)$ 为左上角、边长为 $len$ 的子矩阵进行一次 顺时针旋转；
• 输入 2 x y len，表示将以 $(x, y)$ 为左上角、边长为 $len$ 的子矩阵进行一次 逆时针旋转。

所有操作完成后，小灰灰希望查询若干个位置的数值。 给定 $d$ 个查询，每个查询给出一个坐标 $(dx_i, dy_i)$，你需要输出最终矩阵中该位置上的数值。

输入格式

第一行输入一个整数 $n$。

第二行输入一个整数 $q$。

接下来 $q$ 行，每行描述一个操作，格式为：op x y len

接下来一行输入一个整数 $d$。

接下来 $d$ 行，每行输入两个整数 $dx_i, dy_i$。

输出格式

输出共 $d$ 行，第 $i$ 行输出一个整数，表示最终矩阵中 $(dx_i, dy_i)$ 位置上的数值。

样例 1 输入

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

样例 1 输出

3
4
9
6

样例 1 解释

两次操作分别对局部子矩阵进行了顺时针与逆时针旋转，最终得到目标位置的结果。

样例 2

见选手目录下的 rotate/rotate2.in 和 rotate/rotate2.ans。 该测试用例满足测试点 $13 \sim 16$ 的约束条件。

样例 3

见选手目录下的 rotate/rotate3.in 和 rotate/rotate3.ans。 该测试用例满足测试点 $17 \sim 20$ 的约束条件。

数据范围

对于 $100\%$ 的数据：

• $1 \le n, q \le 10^5$
• $1 \le d \le 10$
• $op \in \{1, 2\}$
• $1 \le x, y, len, dx_i, dy_i \le n$
• $x + len - 1 \le n$
• $y + len - 1 \le n$

各测试点的附加限制如下表所示：

点击下载大样例