CF715D Create a Maze

ZS the Coder 喜欢迷宫。你的任务是创建一个迷宫，让他玩。一个迷宫由 $n \times m$ 个房间组成，房间排列成 $n$ 行（从上到下编号为 $1$ 到 $n$）和 $m$ 列（从左到右编号为 $1$ 到 $m$）。位于第 $i$ 行第 $j$ 列的房间记为 $(i, j)$。玩家从房间 $(1, 1)$ 出发，希望抵达房间 $(n, m)$。 每个房间（除位于迷宫边界的房间外）都有四扇门，分别位于四个墙壁上，两个相邻房间共用一扇门。一些门是锁住的，玩家不能通过被锁住的门。例如，如果连接房间 $(i, j)$ 和 $(i, j+1)$ 的门被锁住，那么玩家就无法从房间 $(i, j)$ 进入房间 $(i, j+1)$。此外，玩家只能向下或向右移动，即从房间 $(i, j)$ 到 $(i+1, j)$ 或从房间 $(i, j)$ 到 $(i, j+1)$，前提是对应的门未被锁住。  上图表示了一个部分门被锁住的迷宫。彩色箭头表示所有可能的路径，红色叉表示被锁住的门。 ZS the Coder 定义一个迷宫的**难度**为 $x$，表示从房间 $(1,1)$ 到房间 $(n,m)$ 恰好有 $x$ 种不同的路径。两条路径不同是指行进过程中经过的房间序列不同。 你的任务是设计一个迷宫，使其难度正好为给定的整数 $T$。此外，ZS the Coder 不喜欢太大的迷宫，因此迷宫的大小和锁住门的数量都有上限限制。看起来很简单，是吧？

输入仅一行，包含一个整数 $T$ $(1 \le T \le 10^{18})$，表示要求的迷宫难度。

* 第一行包含两个整数 $n$ 和 $m$ $(1 \le n, m \le 50)$，表示迷宫的行数和列数。 * 第二行包含一个整数 $k$ $(0 \le k \le 300)$，表示迷宫中被锁住门的数量。 * 接下来 $k$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，表示连接房间 $(x_1, y_1)$ 和房间 $(x_2, y_2)$ 的门被锁住。其中，房间 $(x_2, y_2)$ 必须是房间 $(x_1, y_1)$ 右侧或下侧相邻的房间，即需满足 $x_2 + y_2 = x_1 + y_1 + 1$，并且同一扇门不允许重复出现。 题目保证至少存在一种方案。如果有多种解，输出任意一种即可。

以下图片展示了上述样例输入和输出的情况，彩色箭头表示所有可能路径，红色叉表示被锁住的门。 **第一个样例：**  **第二个样例：**