Sorting

Interview

Time limit0.5sMemory limit256 MB

Summary

Given N and M, construct a permutation of 1..N for which insertion sort performs exactly M shifts, or report that it is impossible.

Level: Medium6 of 10
Topics: Greedy, Sorting, Array, Implementation
Solved: No attempts yet

Problem

Given a permutation $A = [A_1, A_2, \dots, A_N]$ of size $N$ , the code below sorts it. A permutation of size $N$ is a sequence in which each integer from $1$ to $N$ appears exactly once.


```
input: n, a[1 .. n]
cnt = 0
for j = 2 to n:
x = a[j]
i = j - 1
while i >= 1 and a[i] > x:

cnt = cnt + 1
a[i+1] = a[i]
i = i-1

a[i+1] = x

| Pseudocode |

When a permutation of length $N$ is sorted, cnt always lies between $0$ and $N \times (N-1)/2$, inclusive. Given two integers $N$ and $M$, find a permutation of length $N$ for which the value of cnt after sorting with the code above is $M$.

Input

The first line contains the number of test cases $T$ . Each test case is a single line containing $N$ and $M$ .

Output

For each test case, output on one line a permutation whose value of cnt is $M$ .

If more than one permutation satisfies the condition, print any one of them.

Constraints

$1 \le N \le 100,000$
$0 \le M \le N \times (N-1)/2$

Examples1

Example 1

Input

Expected output