De Bruijn sequences (1) P85110

A binary de Bruijn sequence of order $n$ is a cyclic sequence of zeros and ones such that every possible subsequence of $n$ consecutive digits appears exactly once. Please compute the lexicographically smallest de Bruijn sequence of order $n$.

Input

Input consists of several cases, each with an integer number $n$ between 1 and 15.

Output

For every case, print the lexicographically smallest de Bruijn sequence of order $n$.

Hint

A “reasonable” backtracking algorithm should be fast enough to get this problem accepted.