10224 - 派对灯

在IOI98的节日宴会上，我们有N(10<=N<=100)盏彩色灯，他们分别从1到N被标上号码。 这些灯都连接到四个按钮：

按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。 按钮2：当按下此按钮，将改变所有奇数号的灯。 按钮3：当按下此按钮，将改变所有偶数号的灯。 按钮4：当按下此按钮，将改变所有序号是3*K+1(K>=0)的灯。例如：1,4,7... 一个计数器C记录按钮被按下的次数。 当宴会开始，所有的灯都亮着，此时计数器C为0。 你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后所有灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。

不会有灯会在输入中出现两次。 第一行: N。 第二行: C最后显示的数值。
第三行: 最后亮着的灯,用一个空格分开，以-1为结束。
第四行: 最后关着的灯,用一个空格分开，以-1为结束。

每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符，第1个字符表示1号灯，最后一个字符表示N号灯。0表示关闭，1表示亮着。这些行必须从小到大排列（看作是二进制数）。 如果没有可能的状态，则输出一行'IMPOSSIBLE'。

Party Lamps IOI 98 To brighten up the gala dinner of the IOI'98 we have a set of N (10 <= N <= 100) colored lamps numbered from 1 to N.

The lamps are connected to four buttons:

Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON. Button 2: Changes the state of all the odd numbered lamps. Button 3: Changes the state of all the even numbered lamps. Button 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0), i.e., 1,4,7,... A counter C records the total number of button presses.

When the party starts, all the lamps are ON and the counter C is set to zero.

You are given the value of counter C (0 <= C <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.

PROGRAM NAME: lamps INPUT FORMAT Line 1: N
Line 2: Final value of C
Line 3: Some lamp numbers ON in the final configuration, separated by one space and terminated by the integer -1.
Line 4: Some lamp numbers OFF in the final configuration, separated by one space and terminated by the integer -1.
No lamp will be listed twice in the input.

SAMPLE INPUT (file lamps.in) 10 1 -1 7 -1

In this case, there are 10 lamps and only one button has been pressed. Lamp 7 is OFF in the final configuration.

OUTPUT FORMAT Lines with all the possible final configurations (without repetitions) of all the lamps. Each line has N characters, where the first character represents the state of lamp 1 and the last character represents the state of lamp N. A 0 (zero) stands for a lamp that is OFF, and a 1 (one) stands for a lamp that is ON. The lines must be ordered from least to largest (as binary numbers).

If there are no possible configurations, output a single line with the single word `IMPOSSIBLE'

SAMPLE OUTPUT (file lamps.out) 0000000000 0101010101 0110110110

In this case, there are three possible final configurations: All lamps are OFF Lamps 1, 4, 7, 10 are OFF and lamps 2, 3, 5, 6, 8, 9 are ON. Lamps 1, 3, 5, 7, 9 are OFF and lamps 2, 4, 6, 8, 10 are ON.