IOI '98 - Setúbal, Portugal

Party Lamps

To brighten up the gala dinner of the IOI '98 we have a set of N (10 ≤ N ≤ 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 ≥ 0), i.e., 1,4,7,…

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 ≤ C ≤ 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.

Input Format

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.

Output Format

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 word "IMPOSSIBLE" (without quotes).

Sample Input

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.

Sample Output

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.

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 21, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The order of the sample output is wrong...

Modification to the problem statement: you can output the lines in any order.