你正在构建一个模拟程序，其中一架无人机正在探索一颗不稳定的环面状行星。从技术上讲，无人机是在一个环面网格上移动——这是一个在两个维度上都循环包裹的矩形网格。该网格由 $r$ 行（从上到下编号为 $1$ 到 $r$）和 $c$ 列（从左到右编号为 $1$ 到 $c$）的单元格组成。每个单元格都有一个特定的海拔高度，为一个正整数。

环面网格。

第二个样例输入中两步移动事件的路径。

无人机最初位于第一行第一列的单元格中。在每一步中，无人机考虑三个单元格：正右方的单元格、右下方的对角线单元格以及右上方的对角线单元格（必要时进行循环包裹）。无人机飞往这三个单元格中海拔高度最高的那一个。

模拟过程中会发生两类事件：

• “move $k$” —— 无人机移动 $k$ 步。
• “change $a$ $b$ $e$” —— 第 $a$ 行第 $b$ 列单元格的海拔高度变为 $e$。

请找出每次 move 事件后无人机的位置。你可以假设在任何时间点，同一列中都不会有三个循环连续的单元格具有相同的高度。因此，无人机的每一步移动都是明确定义的。

输入格式

第一行包含两个整数 $r$ 和 $c$ ($3 \le r, c \le 2\,000$)，表示环面网格的行数和列数。接下来的 $r$ 行中，第 $i$ 行包含 $c$ 个整数 $e_{i,1}, e_{i,2}, \dots, e_{i,c}$ ($1 \le e_{i,j} \le 10^9$)，表示第 $i$ 行单元格的初始海拔高度。

接下来的一行包含一个整数 $m$ ($1 \le m \le 5\,000$)，表示事件的数量。接下来的 $m$ 行中，第 $j$ 行包含第 $j$ 个事件，格式为 “move $k$”（其中 $k$ 为整数，$1 \le k \le 10^9$）或 “change $a$ $b$ $e$”（其中 $a, b, e$ 为整数，$1 \le a \le r, 1 \le b \le c, 1 \le e \le 10^9$）。

输出格式

输出 $w$ 行，其中 $w$ 是输入中 move 事件的数量。第 $j$ 行应包含输入中第 $j$ 次 move 事件后无人机的位置（行号和列号）。

样例

样例输入 1

4 4
1 2 9 3
3 5 4 8
4 3 2 7
5 8 1 6
4
move 1
move 1
change 1 4 100
move 1

样例输出 1

4 2
1 3
1 4

样例输入 2

3 4
10 20 30 40
50 60 70 80
90 93 95 99
3
move 4
change 2 1 100
move 4

样例输出 2

3 1
2 1