Valera 有一个由 n 行和 m 列组成的矩形表。瓦莱拉对表格行从 1 开始,从上到下进行编号,对列进行编号——从 1 开始,从左到右。我们将用一对整数 (x, y) 来表示位于 x 行和 y 列交叉处的单元格。
Valera 想在他的矩形桌子上放置恰好 k 个管子。管是这样的表格单元格序列 (x1, y1), (x2, y2), ..., (xr, yr),即:
- r ≥ 2;
- 对于任意整数 i (1 ≤ i ≤ r - 1),以下方程 |xi - xi + 1| + |yi - yi + 1| = 1成立;
- 属于该管的每个表格单元格必须在序列中恰好出现一次。
Valera 认为如果满足以下条件,管子就会以奇特的方式排列:
- 没有一对管具有共同的细胞;
- 表格的每个单元格都属于某个管。
帮助 Valera 以一种奇特的方式在他的矩形桌子上排列 k 个管子。
输入
第一行包含三个空格分隔的整数 n、m、k (2 ≤ n, m ≤ 300; 2 ≤ 2k ≤ n·m) — 相应的行数、列数和管数。
输出
打印 k 行。在第 i 行中打印第 i 个管的描述:首先打印整数 ri(管单元的数量),然后打印 2ri 整数 xi1, yi1, xi2, yi2, ..., xiri, yiri(表格单元的序列)。
如果有多个解决方案,您可以打印其中任何一个。保证至少存在一个解。
示例
输入 #1
3 3 3
输出 #1
3 1 1 1 2 1 3 3 2 1 2 2 2 3 3 3 1 3 2 3 3
输入 #2
2 3 1
输出 #2
6 1 1 1 2 1 3 2 3 2 2 2 1
注意
第一个样本的图片:
第二个样本的图片: