We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. Lena Sort

Lena Sort

Lena developed a sorting algorithm described by the following pseudocode:

lena_sort(array nums) {
    if (nums.size <= 1) {
        return nums;
    }
    pivot = nums[0];
    array less;
    array more;
    for (i = 1; i < nums.size; ++i) {
    	// Comparison
        if (nums[i] < pivot) {
            less.append(nums[i]);
        }
        else {
            more.append(nums[i]);
        }
    }
    sorted_less = lena_sort(less);
    sorted_more = lena_sort(more);
    ans = sorted_less + pivot + sorted_more;
    
    return ans;
}

We consider a comparison to be any time some is compared with .

You must solve queries where each query consists of some and . For each query, construct an array of distinct elements in the inclusive range between and that will be sorted by in exactly comparisons, then print each respective element of the unsorted array as a single line of space-separated integers; if no such array exists, print -1 instead.

Input Format

The first line contains a single integer denoting (the number of queries).
Each line of the subsequent lines contains two space-separated integers describing the respective values of (the length of the array) and (the number of comparisons) for query .

Constraints

  • the sum of over all queries

Output Format

Print the answer to each query on a new line. For each query , print space-separated integers describing each respective element in an unsorted array that Lena's algorithm will sort in exactly comparisons; if no such array exists, print -1 instead.

Sample Input 0

2
5 6
5 100

Sample Output 0

4 2 1 3 5
-1

Explanation 0

We perform the following queries:

  1. One array with elements is . The sequence of sorting operations looks like this:

    • Run on . Compare with , , , and for a total of comparisons. We're then left with and ; we only need to continue sorting , as is sorted with respect to itself because it only contains one element.
    • Run on . Compare with and for a total of comparisons. We're then left with and , so we stop sorting.

    We sorted in comparisons and , so we print 4 2 1 3 5 on a new line.

  2. It's not possible to construct an array with elements that will sort in exactly comparisons, so we print -1 on a new line.

Sample Input 1

3
1 0
4 6
3 2

Sample Output 1

1
4 3 2 1
2 1 3

Explanation 1

We perform the following queries:

  1. We want an array with element that sorts in comparisons; any array with element is already sorted (i.e., performs comparisons), so we choose as our array and print 1 on a new line.

  2. One array with elements is ; sorting it with looks like this:

    • on . Compare with , , and for a total of comparisons. We're then left with and ; we only need to continue sorting , as is empty.
    • Run on . Compare with and for a total of comparisons. We're then left with and , so we only continue sorting .
    • Run on . Compare with for a total of comparison. We then stop sorting, as and .

    We sorted in comparisons and , so we print 4 3 2 1 on a new line.

  3. One array with elements is . When we run on it, we compare with and for a total of comparisons. We're then left with and , so we stop sorting.

    We sorted in comparisons and , so we print 2 1 3 on a new line.