Mount Allison Programming Showdown 2019

Start

2019-03-16 16:00 UTC

Mount Allison Programming Showdown 2019

End

2019-03-16 21:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -219 days 15:14:05

Time elapsed

5:00:00

Time remaining

0:00:00

Problem D
Equinumerous

/problems/equinumerous/file/statement/en/img-0001.png
The Modern Arithmetic Puzzle Society (MAPS) has developed a new arithmetic puzzle for its members. This latest puzzle is based on equinumerous numbers. A nonnegative integer $m$ is equinumerous if the canonical base-$2$ representation of $m$ has an equal number of $0$’s and $1$’s when leading zeroes are ignored. So, for example, $9=1001_2$ is equinumerous, but $6=110_2$ is not. Note that MAPS defines the number $0$ to be equinumerous, since it has no $0$’s and no $1$’s in its base-$2$ representation once leading zeroes are ignored. A puzzle consists of two positive integers $n$ and $k$. A solution to the puzzle is a sequence of $k$ equinumerous numbers that sum to $n$. Before MAPS releases its new puzzles to its members, it wants to verify that its puzzles have solutions. You have been enlisted to find a solution to each puzzle, or otherwise report that a puzzle has no solution.

Input

The first line of input is an integer $T$, the number of puzzles in the input file, satisfying $1\leq T\leq 100$. Each of the next $T$ lines contain two space-separated integers $n$, $k$, satisfying $1\leq n\leq 10^{18}$ and $2\leq k\leq 20$, where $n$ is the target sum, and $k$ is the number of equinumerous summands to be used in a solution to the puzzle.

Output

For each puzzle consisting of integers $n$, $k$, output one line with $k$ space-separated equinumerous integers that sum to $n$ if there is a solution to the puzzle. These integers should be in the usual base-$10$ representation. Otherwise, output the word “Impossible”. If there are multiple solutions to a puzzle, then output any one of them.

Sample Input 1 Sample Output 1
3
2 2
7 2
77 4
2 0
Impossible
10 56 9 2