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,\ldots~
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.
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~.
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. 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~. You may output the lines in any order.
If there are no possible configurations, output a single line with the
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.
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~.