C2. Colorful Subarrays (Hard Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference is that in this version $$${1 \leq k \leq 5000}$$$ and sum of $$$n$$$ over all test cases does not exceed $$$5\times 10^6$$$.

An array is called colorful array if and only if all its numbers are distinct.

You are given three integers $$$n$$$, $$$m$$$, and $$$k$$$.

Your task is to construct an array $$$a$$$ of size $$$n$$$ satisfying:

  • $$$1 \le a_i \le k$$$.
  • The count of colorful subarrays among all $$$\frac{n(n+1)}{2}$$$ subarrays of $$$a$$$ is exactly $$$m$$$.
Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

Each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 5000$$$, $$$0 \leq m \leq \frac{n(n+1)}{2}$$$, $$$\bf{1 \leq k \leq 5000}$$$).

NOTE: It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\times 10^6$$$.

Output

If such an array doesn't exist, output $$$-1$$$.

Otherwise, output $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ in a new line.

Example
Input
6
1 1 3
2 3 3
2 1 3
4 5 3
4 10 7
4 6 5
Output
1 
2 1
-1
2 1 1 1
4 5 6 7
1 4 4 5
Note

In the fourth test case, $$$a=[2,1,1,1]$$$ has exactly $$$5$$$ colorful subarrays $$$[a_1]$$$, $$$[a_2]$$$, $$$[a_3]$$$, $$$[a_4]$$$, and $$$[a_1,a_2]$$$.