Maximizing Cosmic Ray Shots

Two players, T and U, are playing a game on an initially empty chessboard of size \(n \times m\). First, player T places \(k\) stones on the board. Then, player U uses his cosmic ray launcher to destroy all the stones. However, his launcher has limited power: in each shot, it can destroy all stones in a single row or a single column.

Player U wants to minimize the number of shots while player T, on the contrary, wants U to launch as many shots as possible. Knowing that U will always use an optimal strategy (i.e. he will choose the minimum number of rows and columns that cover all the stones), player T needs your help to place the \(k\) stones in such a way that the number of launches (i.e. the size of the minimum row/column cover) is maximized.

Note: By König's theorem, the minimum number of rows and columns needed (i.e. the minimum cover) equals the maximum number of stones placed in distinct rows and columns. Therefore, the maximum number of shots U will be forced to use is \(\min(k, \min(n, m))\). In other words, if \(k \ge \min(n, m)\) then T can force U to use \(\min(n, m)\) shots, otherwise the maximum shots is simply \(k\).

Your task is to output a valid configuration of \(k\) stones, each represented by its row and column (1-indexed), such that there are at least \(\min(k, \min(n, m))\) stones placed on distinct rows and columns. One simple approach is to first place stones along the diagonal (i.e. positions \((1,1), (2,2), \ldots\) up to \(\min(n, m)\)) and then place the remaining stones arbitrarily.

inputFormat

The input consists of one line containing three integers separated by spaces: \(n\), \(m\) and \(k\) \( (1 \le n, m \le 10^5,\ 1 \le k \le n \times m)\).

outputFormat

Output exactly \(k\) lines. Each line should contain two integers \(r\) and \(c\) representing the row and column (1-indexed) of a stone. The configuration must be such that the number of shots required (i.e. the size of a minimum set of rows and columns covering all stones) is maximized.

sample

3 3 2

1 1
2 2