题目描述

为了给IOI'98的晚宴增添光彩，我们准备了一组编号从1到N的彩色灯泡。这些灯泡连接到四个按钮：

• 按钮1：按下此按钮时，所有灯泡的状态都会改变：原本亮着的会熄灭，原本熄灭的会亮起。
• 按钮2：改变所有奇数编号灯泡的状态。
• 按钮3：改变所有偶数编号灯泡的状态。
• 按钮4：改变编号为$3K+1$（其中$K \geq 0$）的灯泡的状态，即编号为1, 4, 7,…的灯泡。

有一个计数器C记录按钮被按下的总次数。

晚宴开始时，所有灯泡都亮着，计数器C设置为零。

现在给定计数器C的值以及部分灯泡的最终状态信息。请编写一个程序，确定所有可能的最终灯泡配置（不重复），且这些配置必须与给定的信息一致。

输入格式

程序从标准输入读取数据。输入包含四行，分别描述灯泡的数量N、按钮按下的次数C，以及最终配置中部分灯泡的状态。

• 第一行：灯泡的数量$N$。
• 第二行：计数器C的最终值。
• 第三行：列出最终配置中已知亮着的灯泡编号，以空格分隔，以-1结尾。
• 第四行：列出最终配置中已知熄灭的灯泡编号，以空格分隔，以-1结尾。

输入参数的范围：

• $10 \leq N \leq 100$
• $1 \leq C \leq 10000$
• 已知亮着的灯泡数量不超过2个。
• 已知熄灭的灯泡数量不超过2个。

输出格式

程序将所有可能的最终配置（不重复）写入标准输出。至少存在一种可能的最终配置。每个可能的配置占一行，每行包含$N$个字符，第一个字符表示灯泡1的状态，最后一个字符表示灯泡$N$的状态。0表示熄灭，1表示亮起。配置按二进制升序排列。

示例输入1

10
1
-1
7 -1

示例输出1

0000000000
0101010101
0110110110