A12265 | Fibonacci Suffix

Let's denote (yet again) the sequence of Fibonacci strings:

$F(0) = $ 0, $F(1) = $ 1, $F(i) = F(i - 2) + F(i - 1)$ , where the plus sign denotes the concatenation of two strings.

Let's denote the lexicographically sorted sequence of suffixes of string $F(i)$ as $A(F(i))$ . For example, $F(4)$ is 01101, and $A(F(4))$ is the following sequence: 01, 01101, 1, 101, 1101. Elements in this sequence are numbered from $1$ .

Your task is to print $m$ first characters of $k$ -th element of $A(F(n))$ . If there are less than $m$ characters in this suffix, then output the whole suffix.

The only line of the input contains three numbers $n$ , $k$ and $m$ ( $1 \le n, m \le 200$ , $1 \le k \le 10^{18}$ ) denoting the index of the Fibonacci string you have to consider, the index of the element of $A(F(n))$ and the number of characters you have to output, respectively.

It is guaranteed that $k$ does not exceed the length of $F(n)$ .

Output $m$ first characters of $k$ -th element of $A(F(n))$ , or the whole element if its length is less than $m$ .