Sign permutation#12211

Sign permutation

2 seconds

256 megabytes

Medium

You're given three integers $n, m, k$ n, m, k. Your task is to construct a permutation of $n$ elements such that exactly $m$ numbers are negative and the sum of all elements is $k$ .

If such permutation does not exist, print $0$ .

Input

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

The only line of each test case contains three integers $n, m, k$ n, m, k $(1 \leq m \leq n \leq 1 0^{6}; - 1 0^{12} \leq k \leq 1 0^{12})$ (1 \le m \le n \le 10^6; -10^{12} \le k \le 10^{12}) — number of elements in the permutation, number of negative numbers, and the obtained sum.

It is guaranteed that the sum of all $n$ for all tests does not exceed $1 0^{6}$ 10^6.

Output

If such permutation $p$ exists, print $\pm p_{1}, \pm p_{2}, ..., \pm p_{n}$ \pm p_1, \pm p_2, ..., \pm p_n, otherwise print $0$ .

Examples

Example 1

Loading

Scoring

Subtask $1$ ( $5$ points): $(m = 1)$ (m=1).
Subtask $2$ ( $10$ points): $(m = 2)$ (m=2).
Subtask $3$ ( $15$ points): $(k = 0)$ (k=0).
Subtask $4$ ( $20$ points): $(1 \leq n \leq 3)$ (1 \le n \le 3)
Subtask $5$ ( $20$ points): $(1 \leq \sum n \leq 100)$ (1 \le \sum n \le 100)
Subtask $6$ ( $30$ points): It is guaranteed that such permutation exists.
Subtask $7$ ( $100$ points): No additional constraints.

n, m, k

(1 \leq t \leq 1 0^{4})

n, m, k

(1 \leq m \leq n \leq 1 0^{6}; - 1 0^{12} \leq k \leq 1 0^{12})

1 0^{6}

\pm p_{1}, \pm p_{2}, ..., \pm p_{n}

(m = 1)

(m = 2)

(k = 0)

(1 \leq n \leq 3)

(1 \leq \sum n \leq 100)