IOI '98 - Setúbal, Portugal

To brighten up the gala dinner of the IOI '98 we have a set of $N$ $(10\le N\le 100)$ coloured 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,\dots$

There is a counter $C$ which 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 information on the final state of some of the lamps. Write a program to determine all the possible final configurations of the $N$ lamps that are consistent with the given information, without repetitions.

Input Specification

The input will have four lines, describing the number $N$ of lamps available, the number $C$ of button presses, and the state of some of the lamps in the final configuration.

• The first line contains the number $N$.
• The second line contains the final value of counter $C$.
• The third line lists the lamp numbers you are informed to be ON in the final configuration, separated by one space and terminated by the integer $-1$.
• The fourth line lists the lamp numbers you are informed to be OFF in the final configuration, separated by one space and terminated by the integer $-1$.

Output Specification

The output must contain all the possible final configurations (without repetitions) of all the lamps. Each possible configuration must be written on a different line. Configurations may be listed in arbitrary order.

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.

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

Sample Input

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.

Sample Output

0000000000
0110110110
0101010101

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.