정렬

면접 대비

시간 제한0.5초메모리 제한256 MB

요약

N과 M이 주어질 때, 삽입 정렬이 정확히 M번의 이동을 수행하도록 1부터 N까지의 순열을 만들거나, 불가능하면 그 사실을 판별한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 배열, 구현
정답자: 아직 제출이 없습니다

문제

크기가 $N$ 인 순열 $A = [A_1, A_2, \dots, A_N]$ 이 있을 때, 아래 코드를 이용하면 순열을 정리할 수 있다. 크기가 $N$ 인 순열은 $1$ 부터 $N$ 까지의 자연수가 한 번씩 등장하는 수열이다.


```
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

| 의사코드 |

길이가 $N$인 순열을 정렬하는 경우 cnt는 항상 $0$ 이상 $N \times (N-1)/2$ 이하이다. 두 정수 $N$과 $M$이 주어졌을 때, 위의 코드를 이용해 정렬이 완료된 후의 cnt의 값이 $M$이 되는 길이가 $N$인 순열을 찾아보자.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, $N$ 과 $M$ 이 주어진다.

출력

각 테스트 케이스마다, 한 줄에 하나씩 cnt의 값이 $M$ 인 순열을 출력한다.

조건을 만족하는 순열이 여럿인 경우 아무 것이나 하나 출력하면 된다.

제한

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

예제1

예제 1

입력

예상 출력