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.

Public test cases

**Input**

2 3 4

**Output**

0011 00010111 0000100110101111

Information

- Author
- Xavier Martínez
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Vuitè Concurs de Programació de la UPC - Semifinal
- Date
- 2010-06-30