Problems
Fibonacci strings
Fibonacci strings
The Fibonacci string is a string that consists of 0 and 1 and hasn't to ones in a row.
Given the lexicographic number of Fibonacci string, you must build the Fibonacci string itself. The lexicographic number is a number in a lexicographically ordered set (i.e. sorted in a natural way). The numbering starts from one.
Input data
Contains two integers: the length of Fibonacci string n (1 ≤ n ≤ 44) and string number k that you must print. It is guaranteed that the string with number k exists.
Output data
Print the k-th Fibonacci string of length n.
Examples
Input example #1
3 3
Output example #1
010
Input example #2
5 5
Output example #2
00101