PSWITCH - Party Switching

no tags 

Seraph is a smart boy who, one day at the time of his birthday he was wearing a lot of lights for the event. The number of lights is installed for as many as N, which are numbered 1 through N. lights are connected to a controller that has 4 buttons. Each button functions as follows:

  1. if this button is pressed, then all light will change the state from OFF to ON or from ON to OFF.
  2. if this button is pressed, then the odd-numbered light will change its state.
  3. if this button is pressed, then the even-numbered light will change its state.
  4. if this button is pressed, all lights are numbered 3K +1 will change its state.

In the controller, there are counter C that count number of button will be pressed. when the initial state, the state of all the lights are ON and the counter C is set to 0. After that you will be given information of light at the end of the show, and you have to count how many kinds of configuration according to the information provided.

Input

The first line containing N (10 <= N <= 100) that indicates number of lamps. The second line is C (1 <= C <= 1000) that indicate the final value of the counter. The third line is lists the number of ON lights at the end of the show, each number separated by a space and the end of the line given the value -1. The fourth line is lists the number of OFF light at the end of the show, each number separated by a space and the end of the line given the value -1.

Output

The possible configurations at the end of the event. There should be no repetitive configuration and output must be in lexicographical. If there is no configuration, print "Impossible".

Example

Input:
10
1
-1
7 -1

Output:
0000000000
0101010101
0110110110

Explanation

There is 10 lamps in that event and you have to press the button once, and at the end of event, lamp number 7 must be OFF.

0 mean that lamp is OFF, 1 mean that lamp is ON.


hide comments
nadstratosfer: 2021-06-04 00:57:44

What does translation of the statement to retarded adds here? Original:
http://olympiads.win.tue.nl/ioi/ioi98/contest/day1/party/party.html

Note the phrasing in original statement: "line lists the lamp numbers you are informed to be ON"; this means if the list is empty, any configuration is valid. My initial solution assumed the list contained all lamps that are allowed to be on, giving me grief with the sample case.

Fun problem, try to write your solution as if c was allowed to be much bigger than allowed here.

Last edit: 2021-06-04 01:02:19
!(NULL): 2011-11-20 13:48:22

easy problem :)

Johannes Laire: 2012-02-28 14:43:39

@irakli: You are correct, this problem is also at USACO's training site and originally it is from IOI 1998 (called "Party Lamps").

To make my USACO solution pass here, I only needed to change "IMPOSSIBLE" to "Impossible".


Added by:[Retired] Fendy Kosnatha
Date:2011-03-10
Time limit:0.100s-0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IOI 1998