Solve the programming task below in a Python markdown code block.
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.