G. Суффиксы Фибоначчи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Давайте введём (ага, опять) последовательность строк Фибоначчи:

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

Ваша задача — вывести $$$m$$$ первых символов $$$k$$$-го элемента $$$A(F(n))$$$. Если в этом суффиксе меньше $$$m$$$ символов, выведите его полностью.

Входные данные

Единственная строка входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$m$$$ ($$$1 \le n, m \le 200$$$, $$$1 \le k \le 10^{18}$$$) — номер рассматриваемой строки Фибоначчи, номер требуемого элемента $$$A(F(n))$$$ и количество символов, которые вы должны вывести, соответственно.

Гарантируется, что $$$k$$$ не больше длины $$$F(n)$$$.

Выходные данные

Выведите $$$m$$$ первых символов $$$k$$$-го элемента $$$A(F(n))$$$, или весь этот элемент, если его длина меньше $$$m$$$.

Примеры
Входные данные
4 5 3
Выходные данные
110
Входные данные
4 3 3
Выходные данные
1