CSES Problem Set

# De Bruijn Sequence

CSES - De Bruijn SequenceCSES - De Bruijn Sequence

 Time limit: 1.00 s Memory limit: 512 MB

Your task is to construct a minimum-length bit string that contains all possible substrings of length $n$. For example, when $n=2$, the string 00110 is a valid solution, because its substrings of length $2$ are 00, 01, 10 and 11.

Input

The only input line has an integer $n$.

Output

Print a minimum-length bit string that contains all substrings of length $n$. You can print any valid solution.

Constraints
• $1 \le n \le 15$
Example

Input:
2

Output:
00110