Cornfield

The owner of a cornfield, Minseok, wants to harvest the corn he grew carefully over the year. The field is a grid with $N$ rows and $M$ columns, and each cell has one corn plant. Minseok measured the value of each plant and assigned distinct integers $1,2,\cdots ,N\times M$.

Minseok starts outside the field. While moving outside the field, he can harvest the corn in any cell adjacent to the outside. Or, inside the field, he can move only through cells where he has already harvested corn, and harvest the corn in the cells directly above, below, left, or right of his current cell.

To control corn production, Minseok harvests only $K$ plants. He repeats $K$ times the process of harvesting the most valuable corn among the plants he can currently harvest. Find the positions of the plants he harvests, in order.

The first line contains integers $N$ and $M$ ($1 \le N, M \le 1\,000$), separated by a space.

From the second line onward, the next $N$ lines each contain $M$ integers separated by spaces. The $j$-th integer on the $i$-th line, $a_{ij}$ ($1 \le a_{ij} \le N \times M$), is the value of the corn in row $i$, column $j$ of the grid.

The last line contains an integer $K$ ($1 \le K \le \min(N \times M, 100\,000)$).

Print $K$ lines. Each line contains the position $i, j$ ($1 \le i \le N$, $1 \le j \le M$) of the corn Minseok harvests, in order. Here $i$ is the row and $j$ is the column of the grid.