Gray Code

The Gray code of length n is the list of all bit-strings of length n that differ in exactly one bit (their Hamming distance is 1).
Given an integer n, you are asked to print the Gray code ( lines).

Input

The input contains a single integer n (1 ≀ n ≀ 16).

Output

The program should print the Gray code. Any valid solution is acceptable.

Examples

Input
Output
1
0 1
2
00 01 11 10
3
000 001 011 010 110 111 101 100
Β 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 25 MB

To check your solution you need to sign in
Sign in to continue