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

시간 제한2초메모리 제한1024 MB

요약

n개의 풀잎과 목표 경로 수 k가 주어질 때, 첫 풀잎에서 마지막 풀잎까지 가는 경로 수가 정확히 k가 되도록 각 풀잎을 정상 또는 부서짐으로 표시한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

Входной файл содержит два целых числа $n$ и $k$ ( $2 \le n \le 1000$ , $0 \le k \le 10^{18}$ ) --- число травинок и различных путей, соответственно.

출력

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

Если ответа не существует, то выведите в выходной файл единственное слово <<Impossible>>.

예제4

예제 1
입력
```
3 1
```
예상 출력
```
1 0 1
```
예제 2
입력
```
3 2
```
예상 출력
```
1 1 1
```
예제 3
입력
```
4 0
```
예상 출력
```
1 0 0 1
```
예제 4
입력
```
566 239
```
예상 출력
```
Impossible
```