Andrew 喜欢卡特兰数（Catalan numbers）。同时，Andrew 也喜欢开玩笑。
他是一位经验丰富的命题人，为训练营准备了许多比赛。在每场比赛中，他都会准备一道题目，该题目以一个整数作为输入，输出一个整数，并且对于输入 $0, 1, 2, 3, 4, 5$ 的答案分别为 $1, 1, 2, 5, 14, 42$。然而，对于更大输入的答案与相应的卡特兰数并不一致。
Andrew 已经准备了如此多的比赛，以至于他缺乏具有这种性质的好题。因此，他决定将创建此类题目的过程自动化。他认为，在确定性有限状态自动机（DFA）中计算特定长度单词数量的问题是一个很好的备选题目池。Andrew 选择了 $k$ —— 作为输入为 $6$ 时所期望的答案，并希望找到一个确定性有限状态自动机，它分别接受长度为 $0, 1, 2, 3, 4, 5, 6$ 的单词数量为 $1, 1, 2, 5, 14, 42, k$，且该自动机的状态数最少。
回想一下，确定性有限状态自动机（DFA）是一个五元组 $(\Sigma, U, S, T, \phi)$，其中 $\Sigma$ 是被称为输入字符集的有限集，$U$ 是有限状态集，$S \in U$ 是初始状态，$T \subset U$ 是接受状态（终态）集，而 $\phi : U \times \Sigma \to U \cup \{\emptyset\}$ 是转移函数。
自动机的输入是 $\Sigma$ 上的字符串 $\alpha$。最初，自动机处于状态 $s$。每一步，自动机读取输入字符串的第一个字符 $c$，并将其状态更改为 $\phi(u, c)$，其中 $u$ 是当前状态。如果 $\phi(u, c) = \emptyset$，自动机立即拒绝 $\alpha$。然后，移除输入字符串的第一个字符，并重复该步骤。如果输入字符串变为空后，自动机处于接受状态，则它接受初始字符串 $\alpha$，否则拒绝它。
给你一个整数 $k$。请构造一个字符集大小至多为 $20$ 的确定性有限状态自动机，使其状态数最少，且该自动机接受的长度为 $0$ 到 $6$ 的单词数量由下表给出。接受的更长单词的数量可以是任意的。
| 长度 | 接受的单词数量 |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
| 5 | 42 |
| 6 | $k$ |
输入格式
输入文件包含多组测试数据。
每组测试数据在单独的一行中包含一个整数 $k$ ($120 \le k \le 140$)。
输入以一行 $n = 0$ 结束。
输出格式
对于每组测试数据，按以下格式输出所要求的确定性自动机。
第一行必须包含两个整数：$n$ —— 状态数，以及 $s$ —— 字符集大小 ($1 \le s \le 20$)。请注意，你必须最小化 $n$，但不需要最小化 $s$。
设状态编号为 $1$ 到 $n$，起始状态为 $1$，字符集的字符编号为 $1$ 到 $s$。
第二行必须包含 $n$ 个整数，指定相应的状态是否为接受状态：如果第 $i$ 个状态是接受状态，则第 $i$ 个整数必须为 $1$；如果第 $i$ 个状态不是接受状态，则为 $0$。
接下来的 $n$ 行，每行必须包含 $s$ 个整数：第 $i$ 行的第 $j$ 个整数必须是 $\phi(i, j)$ 的值 —— 即从第 $i$ 个状态通过第 $j$ 个字符转移到的状态，如果 $\phi(i, j) = \emptyset$，则为 $0$。
样例
输入样例 1
131 0
输出样例 1
3 4 1 0 0 1 2 0 0 1 2 2 3 2 3 3 0
说明
在给定的样例中，如果 $\Sigma = \{a, b, c, d\}$，则自动机接受的 $5$ 个长度为 $3$ 的单词为 "aaa"、"aba"、"baa"、"bba" 和 "bca"。