Fibonacci Suffix

1000ms

262144K

Description:

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.

Input:

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:

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

Sample Input:

4 5 3

Sample Output:

Sample Input:

4 3 3

Sample Output:

Informação

Provedor Codeforces

Código CF1065G