Monotone Gray Code

Special Judge Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      A Gray code of order n is the sequence of all binary vectors of length n such that two adjacent vectors differ in exactly one bit. An example of the Gray code for n = 3 is shown on the following figure.

000
001
011
010
110
111
101
100

      The Gray code is called monotone if for any k, no vector with k + 2 or more ones ever appears before a vector with k ones. For example, the code above is not monotone, because the vector 111 appears before the vector 100. An example of the monotone Gray code for n = 3 is shown below.

000
001
011
010
110
100
101
111

      It can be shown that for any n there exists a monotone Gray code. Given n find the monotone Gray code for binary vectors of length n.

Input

The input file contains one integer number n (1 ≤ n ≤ 16).

Output

      Output the monotone Gray code for binary vectors of length n, one vector on a line.

Sample Input

3

Sample Output

000
001
011
010
110
100
101
111

Source

Andrew Stankevich Contest 23

Manager

Information
Solved Number1
Submit Number112
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel