C. Ordered Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a permutation$$$^{\text{∗}}$$$ $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$. We can introduce the following sum for it$$$^{\text{†}}$$$:

$$$$$$S(p) = \sum_{1 \le l \le r \le n} \min(p_l, p_{l + 1}, \ldots, p_r)$$$$$$

Let us consider all permutations of length $$$n$$$ with the maximum possible value of $$$S(p)$$$. Output the $$$k$$$-th of them in lexicographical$$$^{\text{‡}}$$$order, or report that there are less than $$$k$$$ of them.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

$$$^{\text{†}}$$$For example:

  • For the permutation $$$[1, 2, 3]$$$ the value of $$$S(p)$$$ is equal to $$$\min(1) + \min(1, 2) + \min(1, 2, 3) + \min(2) + \min(2, 3) + \min(3) =$$$ $$$1 + 1 + 1 + 2 + 2 + 3 = 10$$$
  • For the permutation $$$[2, 4, 1, 3]$$$ the value of $$$S(p)$$$ is equal to $$$\min(2) + \min(2, 4) + \min(2, 4, 1) + \min(2, 4, 1, 3) \ +$$$ $$$ \min(4) + \min(4, 1) + \min(4, 1, 3) \ +$$$ $$$\min(1) + \min(1, 3) \ +$$$ $$$\min(3) =$$$ $$$2 + 2 + 1 + 1 + 4 + 1 + 1 + 1 + 1 + 3 = 17$$$.

$$$^{\text{‡}}$$$An array $$$a$$$ is lexicographically smaller than an array $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$; or
  • in the first position where $$$a$$$ and $$$b$$$ differ, the array $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{12}$$$) — the length of the permutation and the index number of the desired permutation.

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

Output

For each test case, if there are less than $$$k$$$ suitable permutations, print $$$-1$$$.

Otherwise, print the $$$k$$$-th suitable permutation.

Example
Input
6
3 2
3 3
4 11
4 6
6 39
7 34
Output
1 3 2 
2 3 1 
-1
2 4 3 1 
-1
2 3 4 5 7 6 1
Note

Let us calculate the required sum for all permutations of length $$$3$$$ (ordered lexicographically):

PermutationValue of $$$S(p)$$$
$$$[1, 2, 3]$$$$$$10$$$
$$$[1, 3, 2]$$$$$$10$$$
$$$[2, 1, 3]$$$$$$9$$$
$$$[2, 3, 1]$$$$$$10$$$
$$$[3, 1, 2]$$$$$$9$$$
$$$[3, 2, 1]$$$$$$10$$$

In the first test case, you have to print the second suitable permutation of length $$$3$$$. Looking at the table, we see that it is the permutation $$$[1, 3, 2]$$$.

In the second test case, you have to print the third suitable permutation of length $$$3$$$. Looking at the table, we see that it is the permutation $$$[2, 3, 1]$$$.