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.