eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Рядки Фібоначчі

Рядки Фібоначчі

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Рядком Фібоначчі називається рядок з символів 0 та 1, який не містить двох одиниць підряд.

Вашим завданням є зао лексикографічним номером рядка Фібоначчі побудувати сам рядок. Лексикографічним номером є номер у лексикографічно упорядкованому (тобто відсортованому звичайним чином) наборі. Нумерація ведеться від одиниці.

Вхідні дані

Містить два цілих числа: довжину рядка Фібоначчі n (1n44), та номер рядка k, який необхідно вивести. Гарантується, що рядок з номером k існує.

Вихідні дані

Виведіть k-ий рядок Фібоначчі довжини n.

Приклад

Вхідні дані #1
3 3
Вихідні дані #1
010
Вхідні дані #2
5 5
Вихідні дані #2
00101
Джерело 2010 ЛКШ. Берендеевы Поляны. Июль. A' Д01