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

This is the easy version of the problem. The only difference is that in this version $$$k = 3$$$ and sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

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{k=3}$$$).

NOTE: It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

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
4
1 1 3
2 3 3
2 1 3
4 5 3
Output
1
1 2
-1
2 1 1 1
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]$$$.