“Lyuboyn” 团队——小男孩 Askhat、中男孩 Sanzhar 和大男孩 Nurbakyt——决定拓宽他们的知识面，学习一点电子学知识。他们发明了一种奇特的机电开关，能以特殊方式修改接收到的模拟信号。他们对自己的发明感到非常满意，并自豪地将其命名为“Lyuboyn 开关”。

准确地说，一个信号可以表示为一个长度为 $N$ 的比特序列，“Lyuboyn 开关”的特性是：它产生的输出信号与输入信号恰好有 $K$ 位不同，且没有两个不同的输入信号产生相同的输出信号。为了让他们的发明更加完美，男孩们增加了最后一个特性：如果二进制参数 $T$ 被设置为 1，则输出的链接序列将是循环的，即如果你从一个信号开始，将其替换为开关的输出，并重复该过程足够多次，在某一点上你将回到最初开始的信号。然而，如果参数 $T$ 被设置为 0，则此特性不成立。

在这项任务中，你需要复现该团队的成就并生成“Lyuboyn 代码”——即开关产生的输出信号到给定输入信号的映射。为了简化问题，你只需要输出如上所述的、以信号 $S$ 开头的输出链接序列。

形式化地，你需要找到一个长度为 $2^N$ 的序列 $f$，由长度为 $N$ 的二进制数（包括前导零）组成，满足：

1. $f_0 = S$
2. 对于任意 $i$ 和 $j$ ($i \neq j$)，$f_i \neq f_j$
3. 对于任意 $i$ ($0 \le i < 2^N - 1$)，$f_i$ 与 $f_{i+1}$ 在二进制表示下恰好有 $K$ 位不同。此外，如果参数 $T$ 等于 1，则该序列必须是循环的，即 $f_{2^N - 1}$ 与 $f_0$ 在二进制表示下也必须恰好有 $K$ 位不同。

输入格式

第一行包含三个整数 $N, K$ 和 $T$ ($2 \le N \le 18, 1 \le K < N, 0 \le T \le 1$)。 第二行包含起始数字 $S$ 的二进制表示。

输出格式

如果不存在这样的序列，打印一行包含 -1。 否则，输出的第一行应包含链接序列中的值个数——$2^N$。 从第 2 行到第 $2^N + 2$ 行，每行应包含一个二进制数——即 $f_{i-2}$ 的值。 如果存在多个有效解，你可以输出其中任意一个。

子任务

本任务包含八个子任务：

1. 样例测试。得 0 分。
2. $N = 4, K = 3, T = 1, S = 0$。得 5 分。
3. $2 \le N \le 18, K$ 为偶数, $T \le 1, S < 2^N$。得 3 分。
4. $2 \le N \le 18, K = 1, T = 1, S = 0$。得 11 分。
5. $2 \le N \le 18, K = 3, T = 0, S = 0$。得 15 分。
6. $2 \le N \le 18, K \cdot 2 < N, T = 0, S < 2^N$。得 18 分。
7. $2 \le N \le 18, K < N, T = 0, S < 2^N$。得 31 分。
8. $2 \le N \le 18, K < N, T = 1, S < 2^N$。原始约束。得 17 分。

样例

输入 1

2 1 1
10

输出 1

4
10
11
01
00