Description

  Gray Code is a binary numeral system where two successive values differ in only one bit. The n-bit-width gray code is the sequence consisting of numbers between 0 and 2^n-1. 

For example, 2-bit-width gray code is the sequence of {00, 01, 11, 10}. 3-bit-width gray code is the sequence of {000, 001, 011, 010, 110, 111, 101, 100}.

Now, we want you to construct the n-bit-width gray code by using the following algorithm.

1. If n = 1, Return {0,1}
2. Let S1 be the sequence of Gray(n-1).
3. Let S2 be the reverse of S1.
4. Add “0” to the head of every element in S1.
5. Add “1” to the head of every element in S2.
6. Return S1 + S2. 

Input

The input includes multiple test cases. 

 

In each test case, the first line contains one integer n. 

1 ≤ n ≤ 11

Output

The multiply lines contains 2^n integers, which indicate the n-bit-width gray code.

Sample Input  Download

Sample Output  Download

Tags

Discuss