## IOI '98 P3 - Party Lamps

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type
##### IOI '98 - Setúbal, Portugal

To brighten up the gala dinner of the IOI '98 we have a set of coloured lamps numbered from to .

The lamps are connected to four buttons:

• Button 1: When this button is pressed, all the lamps change their state: those that are are turned and those that are are turned .
• 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 with , i.e.,

There is a counter which records the total number of button presses.

When the party starts, all the lamps are and the counter is set to zero.

You are given the value of counter and information on the final state of some of the lamps. Write a program to determine all the possible final configurations of the lamps that are consistent with the given information, without repetitions.

#### Input Specification

The input will have four lines, describing the number of lamps available, the number of button presses, and the state of some of the lamps in the final configuration.

• The first line contains the number .
• The second line contains the final value of counter .
• The third line lists the lamp numbers you are informed to be in the final configuration, separated by one space and terminated by the integer .
• The fourth line lists the lamp numbers you are informed to be in the final configuration, separated by one space and terminated by the integer .

#### Output Specification

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 characters, where the first character represents the state of lamp 1 and the last character represents the state of lamp . A 0 (zero) stands for a lamp that is , and a 1 (one) stands for a lamp that is . You may output the lines in any order.

If there are no possible configurations, output a single line with the word IMPOSSIBLE.

#### Sample Input

10
1
-1
7 -1

In this case, there are 10 lamps and only one button has been pressed. Lamp 7 is in the final configuration.

#### Sample Output

0000000000
0110110110
0101010101

In this case, there are three possible final configurations:

• All lamps are .
• Lamps are , and lamps are .
• Lamps are , and lamps are .