Reverse Grasshopper

Time limit2sMemory limit1024 MB

Summary

Given n blades and a target k, output which blades are intact so the grasshopper has exactly k jump paths from the first blade to the last, or report Impossible.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Implementation
Solved: No attempts yet

Statement

Along a park path, $n$ blades of grass grow in a row. A grasshopper stands on the first blade and wants to reach the last blade, number $n$ , by jumping. Each jump can go only one or two blades forward. Some blades are broken, and the grasshopper cannot land on them. Knowing which blades are broken, and assuming that the first and last blades are not broken, one can count the number of paths the grasshopper can take from the first blade to the last. Vova solved this problem quickly and came up with a reverse version of it.

In this problem you are asked to solve that reverse problem. Find a description of the blades such that the grasshopper has exactly $k$ different paths.

Input

The input file contains two integers $n$ and $k$ ( $2 \le n \le 1000$ , $0 \le k \le 10^{18}$ ), the number of blades and the number of different paths.

Output

Print a single line with $n$ numbers separated by spaces, describing the blades. A broken blade is written as 0, and an intact blade as 1. The first and last blades must be intact. If there are several answers, print any of them.

If no answer exists, print the word Impossible.

Examples4

Example 1
Input
```
3 1
```
Expected output
```
1 0 1
```
Example 2
Input
```
3 2
```
Expected output
```
1 1 1
```
Example 3
Input
```
4 0
```
Expected output
```
1 0 0 1
```
Example 4
Input
```
566 239
```
Expected output
```
Impossible
```