P4739 [CERC2017] Donut Drone

你正在构建一个模拟，其中一架无人机在一个不稳定的环形星球上探索。技术上来说，无人机在一个环形网格上移动——一个在两个维度上都循环连接的矩形网格。网格由 $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},...,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` 事件后无人机的位置（行号和列号）。

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