K. Mad MAD Sum III
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two even integers $$$n$$$ and $$$m$$$.

We define the $$$\operatorname{MAD}$$$ (Maximum Appearing Duplicate) of an array as the largest number that appears at least twice in the array. If there is no number that appears at least twice, the $$$\operatorname{MAD}$$$ value is $$$0$$$.

For example, $$$\operatorname{MAD}([1, 2, 1]) = 1$$$, $$$\operatorname{MAD}([2, 2, 3, 3]) = 3$$$, $$$\operatorname{MAD}([1, 2, 3, 4]) = 0$$$.

Construct an array $$$a$$$ of length $$$n$$$ satisfying:

  • $$$0 \leq a_i \leq n$$$ for all $$$1 \le i \le n$$$;
  • $$$\displaystyle \sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])=m. $$$

If no such array exists, output $$$-1$$$ instead.

Input

The first line contains one positive integer $$$t\;(1\leq t \leq 10^3)$$$ — the number of test cases.

Each test case consists of one line which contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \le 10^4$$$, $$$0 \le m \le \frac{n \cdot n \cdot (n-1)}{2}$$$). It is guaranteed that $$$n$$$ and $$$m$$$ are both even.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$10^4$$$.

Output

For each test case, output an array $$$a$$$ of length $$$n$$$ that satisfies the given conditions. If no such array exists, output $$$-1$$$ instead.

Example
Input
4
2 0
4 10
4 22
8 40
Output
0 0
4 2 2 4
-1
5 2 1 2 1 5 2 1
Note

In the first test case, $$$$$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])=\operatorname{MAD}([a_1,a_2])=\operatorname{MAD}([0,0])=0. $$$$$$

In the second test case, the following table summarizes the $$$\operatorname{MAD}$$$ of each subarray. $$$$$$ \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & & 0 & 2 & 4 \\ 2 & & & 2 & 2 \\ 3 & & & & 0 \\ 4 & & & & \end{array} $$$$$$ The sum of all $$$\operatorname{MAD}$$$ values is $$$10$$$, as required.

In the third test case, it is impossible to construct such an array.