Description

At the IOI 1998 holiday banquet, we have $n$ colored lamps, numbered from 1 to $n$. These lamps are connected to four buttons:

• Button $1$: When pressed, it toggles all lamps: lamps that are on turn off, and lamps that are off turn on.
• Button $2$: When pressed, it toggles all lamps with odd indices.
• Button $3$: When pressed, it toggles all lamps with even indices.
• Button $4$: When pressed, it toggles all lamps whose indices are $3k+1 \ (k \in [0,+\infty) \cap \mathbb Z)$. For example: 1, 4, 7, 10, …

A counter $c$ records how many times buttons have been pressed. When the banquet starts, all lamps are on, and the counter $c$ is 0.

You are given the value on the counter $c$ and the final states of some lamps after several operations. Write a program to find all possible final states of the lamps that are consistent with the given information, without duplicates.

Input Format

The first line contains a positive integer $n$.
The second line contains an integer $c$, the final value of the counter.

The third line contains several integers, indicating the lamps that are on in the end, terminated by -1.

The fourth line contains several integers, indicating the lamps that are off in the end, terminated by -1.

It is guaranteed that no lamp appears twice in the input.

Output Format

Each line contains one possible final state of all lamps (without duplicates).

Each line has $n$ characters. The $i$-th character corresponds to lamp $i$. 0 means off, and 1 means on. These lines must be sorted from small to large when viewed as binary numbers.

If there is no possible state, output a single line IMPOSSIBLE.

10
1
-1
7 -1

0000000000
0101010101
0110110110

Hint

Constraints
For $100\%$ of the testdata, $10 \le n \le 100$, $0 \le c \le 10^4$.

Sample explanation
In this sample, there are three possible states:

• All lamps are off.
• Lamps 1, 4, 7, 10 are off; 2, 3, 5, 6, 8, 9 are on.
• Lamps 1, 3, 5, 7, 9 are off; 2, 4, 6, 8, 10 are on.

Translation from NOCOW.

Translated by ChatGPT 5