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 10\,000)~ 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.