IOI98 Lamps Puzzle

At the IOI98 festival banquet, there are \(n\) colored lamps numbered from \(1\) to \(n\). Initially, all lamps are turned on. These lamps are connected to 4 buttons as described below:

• Button 1: When pressed, it toggles (i.e. turns on lamps that are off and turns off lamps that are on) all the lamps.
• Button 2: When pressed, it toggles all the odd-numbered lamps.
• Button 3: When pressed, it toggles all the even-numbered lamps.
• Button 4: When pressed, it toggles all lamps whose numbers are of the form \(3k+1\) for \(k \ge 0\) (i.e. lamps 1, 4, 7, 10, ...).

A counter \(c\) records the total number of button presses. At the start, \(c=0\). After some unknown sequence of operations (with the final number of presses exactly \(c\)), some information about the final state of some lamps is provided. Your task is to determine all possible final states of the lamps (each state is a binary string of length \(n\) where '1' indicates an on lamp and '0' indicates an off lamp) that are consistent with the given information. No duplicate states should be printed. The answers must be printed in ascending lexicographical order. If no configuration is possible, print IMPOSSIBLE.

inputFormat

The input consists of three lines:

1. The first line contains two integers \(n\) and \(c\), where \(n\ (1 \le n \le 100)\) is the number of lamps and \(c\ (0 \le c \le 10000)\) is the total number of button presses.
2. The second line contains a list of integers terminated by \(-1\). These integers denote the lamp numbers that must be on in the final configuration. If there are no such lamps, the line will just contain \(-1\).
3. The third line contains a list of integers terminated by \(-1\). These integers denote the lamp numbers that must be off in the final configuration. If there are no such lamps, the line will just contain \(-1\).

Note: The lamp numbers are in the range \(1\) to \(n\).

outputFormat

Output all possible final configurations, each on a separate line, in ascending lexicographical order. Each configuration should be a binary string of length \(n\) where '1' represents an on lamp and '0' represents an off lamp. If there is no configuration that meets the conditions, output a single line containing IMPOSSIBLE.

sample

10 1
-1
-1

0000000000
0101010101
0110110110
1010101010