You are given a sequence of n bits of N 1’s (say “1111111111”)

There are four possible operations types:

Flip all the bits. Flip even position bits. Flip odd position bits. Flip the 3k+1 position bits. The initial configurations is always all 1’s.

Given number of operations, find all possible final configurations satisfying constraints given in input.

Input format:

N <- number of bits . 10 <= N <= 100

C <- number of operations allowed 1 <= C <= 10000

A <- comma separated list of positions which should be 1’s (list has 2 elements max)

This string contains -1 if no restriction on 1’s.

B <- comma separated list of positions which should be 0’s (list has 2 elements max)

This string contains -1 if no restriction on 0’s.

Output format:

It will be a string containing all final combinations separated by #, Combination of bits should be in numerical ascending order in the output string.

For example, if we have two final combinations '0110110110' and '0101010101' then the correct output will be "0101010101#0110110110" not "0110110110#0101010101".

NOTE: Strings are one-indexed.

Sample Test Case 1

Input

10 1 -1 7

Output

0000000000#0101010101#0110110110

Explanation

In this case, there are three possible final combinations:

All bits are 0s

1, 4, 7, 10 are 0s, and 2, 3, 5, 6, 8, 9 are 1′s.

1, 3, 5, 7, 9 are 0’s, and 2, 4, 6, 8, 10 are 1’s

Sample Test Case 2

Input

40 3 16 2,25

Output

0011100011100011100011100011100011100011