CF1065G 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 $ .