题目描述

You are building a simulation in which a drone explores a volatile torus-shaped planet. Technically,the drone is moving across a toroidal grid — a rectangular grid that wraps around circularly in both dimensions. The grid consists of cells organized into $r$ rows numbered $1$ through $r$ top to bottom and $c$ columns numbered $1$ through $c$ left to right. Each grid cell has a certain elevation — a positive integer.

The drone is initially located in the cell in the first row and first column. In each step the drone considers three cells: the cell directly to the right, the cell diagonally right-down and the cell diagonally right-up (wrapping around if necessary). The drone flies to the cell with the largest elevation of the three.

Two types of events may happen during the simulation:

• “move k” — The drone makes $k$ steps.
• “change a b e” — The elevation of the cell in row $a$ column $b$ changes to $e$.

Find the drone’s position immediately after each move event. You may assume that at each point in time, no sequence of three circularly consecutive cells in the same column will have the same elevation. Hence, each drone step is well defined.

输入格式

The first line contains two integers $r$ and $c(3 \le r,c \le 2 000)$ — the number of rows and the number of columns of the toroidal grid. The $i-th$ of the following $r$ lines contains a sequence of $c$ integers $e_{i,1},e_{i,2},...,e_{i,c}(1 \le e_{i,j} \le 10^9)$ — the initial elevations of cells in row $i$.

The following line contains an integer $m(1 \le m \le 5 000)$ — the number of events. The $j-th$ of the following $m$ lines contains the $j-th$ event and is either of the form “move k” where $k$ is an integer such that $1 \le k \le 10^9$ or “change a b e” where $a,b$ and $e$ are integers such that $1 \le a \le r, 1 \le b \le c$ and $1 \le e \le 10^9$.

输出格式

Output $w$ lines where $w$ is the number of move events in the input — the $j-th$ line should contain the drone’s position (row and column numbers) after the $j-th$ move event in the input.

题目大意

输入一个循环矩阵（即第一行的上一行是最后一行，最后一行的下一行是第一行，最后一列的下一列是第一列）。你的初始位置在 $(1,1)$，每一步会走向右上、右、右下三个格子中权值最大的一个格子。

支持两种操作：

• 修改一个格子的权值
• 从当前位置走 $k$ 步，并输出目标位置

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