A9291 | Inna and Sweet Matrix

The first line of the input contains three integers $n$ , $m$ and $k$ $(1<=n,m<=50,1<=k<=n·m)$ .

In the first line print an integer — Inna's minimum penalty in the game.

In the next $k$ lines print the description of the path for each candy. The description of the path of the candy that is placed $i$ -th should follow on the $i$ -th line. The description of a path is a sequence of cells. Each cell must be written in the format $(i,j)$ , where $i$ is the number of the row and $j$ is the number of the column. You are allowed to print extra whitespaces in the line. If there are multiple optimal solutions, print any of them.

Please follow the output format strictly! If your program passes the first pretest, then the output format is correct.

Note to the sample. Initially the matrix is empty. Then Inna follows her first path, the path penalty equals the number of cells in it — 3. Note that now no path can go through cell (2, 2), as it now contains a candy. The next two candies go to cells (1, 2) and (2, 1). Inna simply leaves the last candy at cell (1, 1), the path contains only this cell. The total penalty is: 3 + 2 + 2 + 1 = 8.

Note that Inna couldn't use cell (1, 1) to place, for instance, the third candy as in this case she couldn't have made the path for the fourth candy.