Description

你正在构建一个模拟，其中一架无人机在一个不稳定的环形星球上探索。技术上来说，无人机在一个环形网格上移动——一个在两个维度上都循环连接的矩形网格。网格由 $r$ 行组成，从上到下编号为 $1$ 到 $r$，以及 $c$ 列，从左到右编号为 $1$ 到 $c$。每个网格单元都有一定的海拔——一个正整数。

无人机最初位于第一行第一列的单元格中。在每一步中，无人机会考虑三个单元格：直接向右的单元格、右下对角线的单元格和右上对角线的单元格（如有必要，进行循环连接）。无人机飞向这三个单元格中海拔最高的那个。

在模拟过程中可能发生两种类型的事件：

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

在每个 move 事件之后，找到无人机的位置。你可以假设在任何时候，同一列中连续的三个循环单元格不会有相同的海拔。因此，每一步无人机的移动都是明确的。

Input Format

第一行包含两个整数 $r$ 和 $c(3 \le r,c \le 2 000)$——环形网格的行数和列数。接下来的 $r$ 行中的第 $i$ 行包含一个 $c$ 个整数的序列 $e_{i,1},e_{i,2},...,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$。

Output Format

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

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

4 2
1 3
1 4

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

3 1
2 1

Hint

题面翻译由 ChatGPT-4o 提供。