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
|