Donut Drone

You are building a simulation of a drone that explores a donut shaped planet. The drone moves over a toroidal grid, a rectangular grid that wraps around in both directions. The grid has $r$ rows numbered $1$ to $r$ from top to bottom and $c$ columns numbered $1$ to $c$ from left to right. Every cell has an elevation, and an elevation is a positive integer.

The drone starts in the cell in row $1$ and column $1$. In each step the drone looks at three cells: the cell directly to the right, the cell diagonally right and down, and the cell diagonally right and up. Row and column numbers wrap around, so row $1$ is below row $r$ and column $1$ is to the right of column $c$. The drone flies to the cell with the largest elevation among the three.

Two kinds of events happen during the simulation.

• move k: the drone takes $k$ steps.
• change a b e: the elevation of the cell in row $a$ and column $b$ becomes $e$.

Find the position of the drone right after each move event.

At every point in time, any three circularly consecutive cells of one column have pairwise different elevations, so the target of each step is always a single cell.

The first line has two integers $r$ and $c$ ($3 \le r, c \le 2000$), the number of rows and the number of columns of the grid. The $i$-th of the next $r$ lines has $c$ integers $e_{i,1}, e_{i,2}, \ldots, e_{i,c}$ ($1 \le e_{i,j} \le 10^9$), the initial elevations of the cells in row $i$.

The next line has an integer $m$ ($1 \le m \le 5000$), the number of events. The $j$-th of the next $m$ lines has the $j$-th event. An event is either move k with $1 \le k \le 10^9$, or change a b e with $1 \le a \le r$, $1 \le b \le c$ and $1 \le e \le 10^9$.

Print one line for each move event of the input, in the order the events appear. The line for the $j$-th move event has the row number and the column number of the cell where the drone stands right after that event, separated by one space.