# Ordered Permutations

## Problem Description

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) $ $ </p><p>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.</p><div class="statement-footnote"><p> $ ^{\\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). </p><p> $ ^{\\text{†}} $ For example: </p><ul> <li> 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 $  </li><li> 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 $ . </li></ul><p> $ ^{\\text{‡}} $ An array  $ a $  is lexicographically smaller than an array  $ b $  if and only if one of the following holds: </p><ul> <li>  $ a $  is a prefix of  $ b $ , but  $ a \\ne b $ ; or </li><li> in the first position where  $ a $  and  $ b $  differ, the array  $ a $  has a smaller element than the corresponding element in  $ b$$$.

## Input Format

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 Format

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

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

## Sample #1

### Sample Input #1

```
6
3 2
3 3
4 11
4 6
6 39
7 34
```

### Sample Output #1

```
1 3 2 
2 3 1 
-1
2 4 3 1 
-1
2 3 4 5 7 6 1
```

## Hint

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] $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, combinatorics, constructive algorithms, greedy, math, two pointers
Difficulty: 1600