Alice gave Bob 3 integers N, K, and S. Help Bob find an S-good sequence.

A sequence B of length N is called S-good if the following conditions are met:
$B_{i} \in$ {-1, 0, 1} for each 1 ≤ i ≤ N
$\sum_{i=1}^N B_{i}\cdot K^{i-1} = S$

If there are multiple S-good sequences, print any of them.
If no S-good sequence exists, print -2.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of a single line of input containing three space-separated integers — N, K, and S.

------ Output Format ------

For each test case:
- If no S-good sequence exists, print -2.
- Otherwise, output N space-separated integers denoting the S-good sequence.

If multiple S-good sequences exist, you may print any of them.

------ Constraints ------

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 100$
$2 ≤ K ≤ 100$
$1 ≤ S ≤ 10^{18}$

----- Sample Input 1 ------
3
4 2 15
3 6 36
5 5 7
----- Sample Output 1 ------
1 1 1 1
0 0 1
-2
----- explanation 1 ------
Test case $1$: We have $B = [1,1,1,1]$ and $S = 15$
$\sum_{i=1}^N B_{i}\cdot K^{i-1} = 1\cdot 1 + 2\cdot 1 + 4\cdot 1 + 8\cdot 1 = 15$, hence $B$ is an $S$-good sequence.

Test case $2$: We have $B = [0, 0, 1]$ and $S = 36$. $6^{2} = 36$ so clearly $B$ is $S$-good.

Test case $3$: No $S$-good sequence of length $5$ exists.

见题面

见题面