P1468 [IOI 1998 / USACO2.2] Party Lamps

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.

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.

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`.

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