CF715D.Create a Maze

ZS the Coder loves mazes. Your job is to create one so that he can play with it. A maze consists of n × m rooms, and the rooms are arranged in n rows (numbered from the top to the bottom starting from 1) and m columns (numbered from the left to the right starting from 1). The room in the i-th row and j-th column is denoted by (i, j). A player starts in the room (1, 1) and wants to reach the room (n, m).

Each room has four doors (except for ones at the maze border), one on each of its walls, and two adjacent by the wall rooms shares the same door. Some of the doors are locked, which means it is impossible to pass through the door. For example, if the door connecting (i, j) and (i, j + 1) is locked, then we can't go from (i, j) to (i, j + 1). Also, one can only travel between the rooms downwards (from the room (i, j) to the room (i + 1, j)) or rightwards (from the room (i, j) to the room (i, j + 1)) provided the corresponding door is not locked.

This image represents a maze with some doors locked. The colored arrows denotes all the possible paths while a red cross denotes a locked door.

ZS the Coder considers a maze to have difficulty x if there is exactly x ways of travelling from the room (1, 1) to the room (n, m). Two ways are considered different if they differ by the sequence of rooms visited while travelling.

Your task is to create a maze such that its difficulty is exactly equal to T. In addition, ZS the Coder doesn't like large mazes, so the size of the maze and the number of locked doors are limited. Sounds simple enough, right?

ZS the Coder 热爱迷宫。你的任务是为他设计一个迷宫，供他玩耍。迷宫由 $n \times m$ 个房间组成，这些房间排列成 $n$ 行（从上到下编号，起始编号为 1）和 $m$ 列（从左到右编号，起始编号为 1）。第 $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 将迷宫的“难度”定义为：从房间 $(1,\,1)$ 到达房间 $(n,\,m)$ 的不同路径总数恰好为 $x$。若两条路径所经过的房间序列不同，则视为不同的路径。

你的任务是构造一个难度恰好等于 $T$ 的迷宫。此外，ZS the Coder 不喜欢过大的迷宫，因此对迷宫尺寸及锁住的门的数量均有限制。听起来很简单，对吧？

The first and only line of the input contains a single integer T (1 ≤ T ≤ 1018), the difficulty of the required maze.

输入仅有一行，包含一个整数 $T$（$1 \leq T \leq 10^{18}$），表示所需迷宫的难度。

The first line should contain two integers n and m (1 ≤ n, m ≤ 50) — the number of rows and columns of the maze respectively.

The next line should contain a single integer k (0 ≤ k ≤ 300) — the number of locked doors in the maze.

Then, k lines describing locked doors should follow. Each of them should contain four integers, _x_1, _y_1, _x_2, _y_2. This means that the door connecting room (_x_1, _y_1) and room (_x_2, _y_2) is locked. Note that room (_x_2, _y_2) should be adjacent either to the right or to the bottom of (_x_1, _y_1), i.e. _x_2 + _y_2 should be equal to _x_1 + _y_1 + 1. There should not be a locked door that appears twice in the list.

It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.

第一行应包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 50$），分别表示迷宫的行数和列数。

第二行应包含一个整数 $k$（$0 \leq k \leq 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$。列表中不应出现重复的上锁门。

保证至少存在一种解。若存在多个解，输出任意一个即可。

Here are how the sample input and output looks like. The colored arrows denotes all the possible paths while a red cross denotes a locked door.

In the first sample case:

In the second sample case:

以下是样例输入与输出的示意图。彩色箭头表示所有可能的路径，红色叉号表示上锁的门。

在第一个样例中：

在第二个样例中：