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

Обратный кузнечик

Обратный кузнечик

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Учитель дал Вове задание решить задачу о кузнечике. Она состоит в следующем.

В парке в ряд растут n травинок. Находясь на первой из них, кузнечик хочет, совершая прыжки, добраться до последней травинки с номером n. При этом кузнечик за один прыжок может прыгать только на одну или две травинки вперед. К несчастью, некоторые травинки сломались и кузнечику нельзя на них прыгать. Зная, какие травинки сломались и считая, что первая и последняя травинки не сломаны, можно найти число путей, которыми кузнечик может добраться с первой травинки до последней. Вова быстро справился с решением этой задачи и придумал к ней обратную.

В настоящей задаче Вам предлагается решить обратную задачу. А именно, найти такое описание травинок в пути кузнечика, что число различных путей кузнечика равно k.

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

Два целых числа n и k (2n1000, 0k10^18) - число травинок и различных путей, соответственно.

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

Выведите через пробел n чисел - описания травинок. Сломанной травинке соответствует число 0, целой - 1. Первая и последняя травинки должны быть целыми. Если существует несколько ответов, то выведите любой.

Если ответа не существует, то выведите слово "Impossible".

Пример

Входные данные #1
3 1
Выходные данные #1
1 0 1
Входные данные #2
3 2
Выходные данные #2
1 1 1
Входные данные #3
4 0
Выходные данные #3
1 0 0 1
Входные данные #4
566 239
Выходные данные #4
Impossible
Автор Владимир Ульянцев
Источник 2011 Цикл Интернет-олимпиад для школьников, Восьмая индивидуальная олимпиада, 27 марта, Задача D