P4739 [CERC2017] Donut Drone

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.