← 返回题目列表

Codeforces · 1065/G

G. 斐波那契后缀

中文机器翻译题面 查看原题

让我们(再次)表示斐波那契字符串的序列:

$$$F(0) = $$$ 0, $$$F(1) = $$$ 1, $$$F(i) = F(i - 2) + F(i - 1)$$$,其中加号表示两个字符串的串联。

让我们将字符串 $$$F(i)$$$ 的后缀按字典顺序排序的序列表示为 $$$A(F(i))$$$。例如,$$$F(4)$$$ 为 01101,$$$A(F(4))$$$ 为以下序列:01, 01101, 1, 101, 1101。此序列中的元素从 $$$1$$$ 开始编号。

您的任务是打印 $$$A(F(n))$$$ 的 $$$k$$$ 第一个元素的 $$$m$$$ 第一个字符。如果该后缀中的字符少于$$$m$$$,则输出整个后缀。

输入

输入的唯一行包含三个数字 $$$n$$$、$$$k$$$ 和 $$$m$$$ ($$$1 \le n, m \le 200$$$, $$$1 \le k \le 10^{18}$$$) 表示您必须考虑的斐波那契字符串的索引,元素的索引$$$A(F(n))$$$ 和您必须输出的字符数。

保证$$$k$$$不超过$$$F(n)$$$的长度。

输出

输出$$$A(F(n))$$$的第$$$k$$$个元素的$$$m$$$第一个字符,或者如果其长度小于$$$m$$$,则输出整个元素。

示例

输入 #1

4 5 3

输出 #1

110

输入 #2

4 3 3

输出 #2

1