CSES - 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