B. WisdomCasual's Deadline
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$\text{WisdomCasual}$$$ was supposed to prepare this problem for the $$$\text{UEPC}$$$ a week ago. Naturally, he forgot.

With only 30 minutes left before $$$\text{cgmoreda}$$$'s deadline, he scribbled down an idea involving arrays and operations. He thinks it is brilliant, but he has no time to solve it or assess its difficulty. He needs you to solve it for him and tell him the difficulty.

Here is the problem he wrote down:

You are given three integers $$$n$$$, $$$k$$$, and $$$x$$$. You need to construct an array $$$a$$$ of $$$n$$$ integers that satisfies the following conditions:

  1. $$$-k \le a_i \le k$$$ for all $$$1 \le i \le n$$$.
  2. The sum of all elements in the array is exactly $$$0$$$: $$$\sum_{i=1}^{n} a_i = 0$$$.
  3. The cost of the array is at most $$$x$$$.

The cost of an array is defined as the minimum number of operations required to make all elements in the array equal to $$$0$$$.

In one operation, you can choose an index $$$i$$$ ($$$1 \le i \lt n$$$) and do exactly one of the following:

  • Decrease $$$a_i$$$ by $$$1$$$ and increase $$$a_{i+1}$$$ by $$$1$$$.
  • Increase $$$a_i$$$ by $$$1$$$ and decrease $$$a_{i+1}$$$ by $$$1$$$.

Since $$$\text{WisdomCasual}$$$ wants to ensure the problem has a unique output, you must find the lexicographically smallest array $$$a$$$ that satisfies all the above conditions. (He doesn't have enough time to write a custom checker)

Can you solve it for him and save his deadline?

Note: An array $$$a$$$ is lexicographically smaller than an array $$$b$$$ of the same length if, at the first index where they differ, the element in $$$a$$$ is strictly smaller than the corresponding element in $$$b$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$)  — the number of test cases.

The only line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le 10^9$$$, $$$0 \le x \le 10^{18}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers representing the lexicographically smallest valid array $$$a$$$.

It is guaranteed that under the given constraints, at least one valid array always exists.

Example
Input
3
3 2 2
4 10 0
3 5 1
Output
-2 2 0 
0 0 0 0 
-1 1 0