题目内容

给定一个 $m$ 行 $n$ 列的矩形网格，所有格子按行优先顺序依次填入从 1 开始的连续正整数。形式化地，编号为 $x$ 的格子所在行坐标为 $\lfloor (x-1)/n \rfloor$，列坐标为 $(x-1)\bmod n$。

一条解锁路径由一个整数序列表示。对于序列中每一对相邻数字 $a$ 和 $b$，需要满足以下两个条件：

• 网格相邻性：设 $a$ 与 $b$ 对应格子的坐标分别为 $(r_a,c_a)$ 和 $(r_b,c_b)$。必须满足 $a \neq b$、$|r_a-r_b| \le 1$ 且 $|c_a-c_b| \le 1$。直观上，这表示两个格子必须处于彼此周围 8 个相邻方向之一。
• 边不重复：将每一对相邻数字视为一条无向边。若数字对 $(a,b)$ 已经出现过，则之后不能再出现 $(a,b)$ 或 $(b,a)$。

现在给出若干候选序列，请找出其中所有满足上述规则的序列。

约束条件

• 行数 $m$ 和列数 $n$ 均为 $1$ 到 $100$ 之间的整数，且 $m \times n \le 100$。
• 候选序列数量 $k$ 满足 $1 \le k \le 5$。
• 每个候选序列至少包含两个整数，所有整数均在 $1$ 到 $m \times n$ 之间。

输入描述

第一行包含一个整数 $m$，表示网格的行数。

第二行包含一个整数 $n$，表示网格的列数。

第三行包含一个整数 $k$，表示候选序列的数量。

接下来 $k$ 行，每行包含一个用逗号分隔的整数序列，代表一个候选解锁路径。

输出描述

按输入顺序输出所有满足条件的候选序列，每行输出一条，格式与输入中的序列一致。

如果没有任何候选序列满足条件，输出 false。

样例1

输入

2
4
4
1,2,6,7,8
1,4,8
1,2,5,2
1,5,6,2,3

输出

1,2,6,7,8
1,5,6,2,3

说明

候选 1,2,6,7,8：1 到 2、2 到 6、6 到 7、7 到 8 均满足相邻条件，行差和列差都不超过 1，且没有重复边，因此合法。

候选 1,4,8：1 与 4 的列坐标差为 $3$，超过允许的 $1$，因此不合法。

候选 1,2,5,2：2→5 已经使用过边 $(2,5)$，之后的 5→2 再次使用同一条无向边，因此不合法。

候选 1,5,6,2,3：所有相邻步均满足 8 邻域条件，边也均未重复，因此合法。

最终按输入顺序输出合法序列。

样例2

输入

3
1
3
1,2,3
1,3
3,2,1,2

输出

1,2,3

说明

这是一个 3 行 1 列的单列网格，编号从上到下依次为 1、2、3。

候选 1,2,3：1→2 和 2→3 均为竖直相邻，行差都是 1，边未重复，因此合法。

候选 1,3：1 与 3 的行差为 2，不满足相邻条件，因此不合法。

候选 3,2,1,2：3→2 和 2→1 合法，但 1→2 再次使用边 $(1,2)$，因此不合法。

所以只有 1,2,3 被输出。

样例3

输入

1
1
1
1,1

输出

false

说明

网格只有 1 个格子，编号只能为 1。

候选 1,1 中相邻两个数字相同，不满足 $a\ne b$ 的条件，因此不合法。

没有合法候选序列，输出 false。