Consider all possible `N`-bit binary configurations. Your task is to find a permutation of these values such that any two consecutive configurations differ by exactly one bit. If there are multiple solutions, all of them are considered correct.

### Input

A single integer: `N`

### Output

The output should contain all ** 2^{N}** configurations, each on a separate line.

Each configuration should consist of exactly

**bits, including leading zeros.**

`N`### Constraints

`1 ≤ N ≤ 12`

### Sample

Input | Output |
---|---|

3 | 000001 011 010 110 100 101 111 |

### Approach #1

Start with the values ** [0, 1]**. At each iteration, do the following:

- reverse the current list and append it to itself
- prepend each element in the first half with a
`0` - prepend each element in the second half with a
`1`

#1 | #2 | #3 | #4 |
---|---|---|---|

01 | 00011110 | 000001011010110111101100 | 0000000100110010011001110101010011001101111111101010101110011000 |

The `N ^{th}` iteration of this process generates all

**bit configurations, in an order which respects the required property.**

`N`#### Haskell implementation

`once` applies a single iteration to a given list.`solve` uses function composition to generate `once` composed to itself `N-1` times, and applies the resulting function to the first iteration.

solve n = foldr (.) id (replicate (n-1) once) ["0", "1"] once xs = map ('0':) xs ++ map ('1':) (reverse xs) main = do input <- getContents let n = read input :: Int sequence $ map putStrLn $ solve n

### Approach #2

Start from the null configuration. Try each of the `N` possible bit flips, and keep track of previously encountered configurations. When a new configuration is found, repeat the same process for it. Stop when no new configuration can be found.

*Note:* a recursive implementation of this approach can result in a stack overflow.