CF390D.Inna and Sweet Matrix

Inna loves sweets very much. That's why she decided to play a game called "Sweet Matrix".

Inna sees an n × m matrix and k candies. We'll index the matrix rows from 1 to n and the matrix columns from 1 to m. We'll represent the cell in the i-th row and j-th column as (i, j). Two cells (i, j) and (p, q) of the matrix are adjacent if |i - p| + |j - q| = 1. A path is a sequence of the matrix cells where each pair of neighbouring cells in the sequence is adjacent. We'll call the number of cells in the sequence the path's length.

Each cell of the matrix can have at most one candy. Initiallly, all the cells are empty. Inna is trying to place each of the k candies in the matrix one by one. For each candy Inna chooses cell (i, j) that will contains the candy, and also chooses the path that starts in cell (1, 1) and ends in cell (i, j) and doesn't contain any candies. After that Inna moves the candy along the path from cell (1, 1) to cell (i, j), where the candy stays forever. If at some moment Inna can't choose a path for the candy, she loses. If Inna can place all the candies in the matrix in the described manner, then her penalty equals the sum of lengths of all the paths she has used.

Help Inna to minimize the penalty in the game.

伊娜非常喜欢糖果。因此，她决定玩一个名为“甜蜜矩阵”的游戏。

伊娜面对一个 $n \times m$ 的矩阵和 $k$ 颗糖果。我们将矩阵的行编号为 $1$ 到 $n$，列编号为 $1$ 到 $m$。用 $(i, j)$ 表示第 $i$ 行、第 $j$ 列的格子。矩阵中两个格子 $(i, j)$ 和 $(p, q)$ 被称为相邻，当且仅当 $|i - p| + |j - q| = 1$。一条路径是指一串矩阵格子组成的序列，其中序列中每一对相邻格子都是相邻的。我们称该序列中格子的个数为该路径的长度。

矩阵中每个格子最多只能放置一颗糖果。初始时，所有格子均为空。伊娜尝试依次将 $k$ 颗糖果逐一放入矩阵中。对于每一颗糖果，伊娜需选择一个将要放置该糖果的格子 $(i, j)$，并同时选择一条从格子 $(1, 1)$ 出发、终点为 $(i, j)$ 且不经过任何已有糖果所在格子的路径。随后，伊娜将这颗糖果沿着该路径从 $(1, 1)$ 移动至 $(i, j)$，此后该糖果便永久停留在 $(i, j)$。若在某一步中，伊娜无法为当前糖果找到满足条件的路径，则她失败。若伊娜能以所述方式成功放置全部 $k$ 颗糖果，则她的惩罚值定义为所使用的所有路径长度之和。

请帮助伊娜最小化游戏中的惩罚值。

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

输入的第一行包含三个整数 $n$、$m$ 和 $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.

第一行输出一个整数——Inna 在游戏中的最小罚分。

接下来的 $k$ 行中，依次输出每颗糖果的路径描述。其中，第 $i$ 颗糖果（即初始放置在第 $i$ 个位置的糖果）的路径描述应输出在第 $i$ 行。路径描述为一系列格子，每个格子需按格式 $(i,\,j)$ 表示，其中 $i$ 为行号，$j$ 为列号。允许在行内输出额外的空白字符。若存在多个最优解，输出任意一个即可。

请严格遵循输出格式！若您的程序通过了第一个预测试，则说明输出格式正确。

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.

样例说明：初始时矩阵为空。随后，因娜沿她的第一条路径行走，该路径的惩罚值等于其经过的格子数——3。注意，此时任何路径都无法再经过格子 (2, 2)，因为该格子中已放置了一颗糖果。接下来两颗糖果分别放置在格子 (1, 2) 和 (2, 1) 中。因娜将最后一颗糖果直接放在格子 (1, 1) 中，该路径仅包含这一个格子。总惩罚值为：$3 + 2 + 2 + 1 = 8$。

注意，因娜不能将第三颗糖果（例如）放在格子 (1, 1) 中，否则她将无法为第四颗糖果构造出合法路径。