← 返回题目列表

Codeforces · 441/C

C. 瓦莱拉和管

中文机器翻译题面 查看原题

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

注意

第一个样本的图片:

第二个样本的图片: