题目描述

To brighten up the gala dinner of the IOI'98 we have a set of $N$ ($10 \le N \le 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 $3k+1$ (with $k \ge 0$), i.e., $1,4,7,\ldots$.

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 \le C \le 10000$) and the final state of some of the lamps after some operations have been executed. Determine all the possible final configurations of the $N$ lamps that are consistent with the given information, without repetitions.

输入格式

• 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.

输出格式

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 stands for a lamp that is OFF, and a 1 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.

10
1
-1
7 -1

0000000000
0101010101
0110110110

提示

Sample explanation

Input

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

Output

In this case, there are three possible final configurations:

• All lamps are OFF.
• Lamps $1,3,5,7,9$ are OFF and lamps $2,4,6,8,10$ are ON.
• Lamps $1,4,7,10$ are OFF and lamps $2,3,5,6,8,9$ are ON.

USACO Training Section 2.2.