Create a Maze

创建一个迷宫，我们规定： 1.迷宫有n列m行，共 m x n 个房间。 2.玩家开始于迷宫的(1,1)位置，而终点在(n,m)位置。 3.除迷宫边界外，每个房间有4个门，每面墙一个，两个相邻的房间有着同一扇门。 4.有些门锁着，这表示是不可能通过这扇门， 例如：连接（i,j）与(i,j+1)房间的门是锁着的，则玩家不能从(i,j)行进至(i,j+1)。 5.玩家只能 向下 或 向右 走。 6.我们定义迷宫的"难度"为完成这个迷宫的方法数。 （当两个通过迷宫方法所走的房间顺序不同，我们就认为这两个方法是不同的） 输入格式： 有且只有一行:一个整数 T(1<=T<=10e18)，表示迷宫的"难度"。 输出格式: 第一行应包括2个整数 n 和 m（1<=n,m<=50）表示迷宫的列数与行数。 第二行应包括1个整数 k(0<=k<=300) 表示迷宫中锁上门的个数。 接下来 k 行描述迷宫中锁上的门。每行 4 个整数：x1,y1,x2,y2。 这表明房间(x1,y1)和房间(x2,y2)之间的门是被锁上的。 应注意房间(x2,y2)应总是在房间(x1,y1)的右方或下方 (就是说 x2+y2=x1+y1+1)。 同一扇锁上的门不应该输出2次。 保证至少有一种解法。 有多个解时，任意输出一个。

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?

The first and only line of the input contains a single integer $ T $ ( $ 1<=T<=10^{18} $ ), the difficulty of the required maze.

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.

3

3 2
0

4

4 3
3
1 2 2 2
3 2 3 3
1 3 2 3

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: