Party Lamps

There are $N$ coloured lamps numbered from $1$ to $N$. The lamps are wired to four buttons:

• Button 1 — toggles every lamp: lamps that are ON turn OFF, and lamps that are OFF turn ON.
• Button 2 — toggles the state of every odd-numbered lamp.
• Button 3 — toggles the state of every even-numbered lamp.
• Button 4 — toggles the state of every lamp whose number has the form $3K+1$ (with $K \ge 0$), i.e. lamps $1, 4, 7, \dots$

A counter $C$ records the total number of button presses.

When the event starts, every lamp is ON and the counter $C$ is $0$.

You are given the value of the counter $C$ and information about the final state of some of the lamps. Determine every possible final configuration of the $N$ lamps that is consistent with the given information, listing each distinct configuration exactly once.

The input consists of four lines describing the number of lamps $N$, the number of button presses $C$, and the known final states of some lamps.

• The first line contains the integer $N$.
• The second line contains the final value of the counter $C$.
• The third line lists the numbers of the lamps known to be ON in the final configuration, separated by single spaces and terminated by the integer $-1$.
• The fourth line lists the numbers of the lamps known to be OFF in the final configuration, separated by single spaces and terminated by the integer $-1$.

Constraints:

• $10 \le N \le 100$
• $1 \le C \le 10000$
• At most $2$ lamps are declared ON.
• At most $2$ lamps are declared OFF.
• At least one valid final configuration always exists.

Output every possible final configuration of the $N$ lamps that is consistent with the input, with no repetitions.

Each configuration is written on its own line as a string of $N$ characters, where the $i$-th character is the state of lamp $i$: 0 means OFF and 1 means ON.

Print the configurations in lexicographically ascending order (so 0000000000 comes before 0101010101).