C. Упорядоченные перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим перестановку$$$^{\text{∗}}$$$ $$$p_1, p_2, \ldots, p_n$$$ чисел от $$$1$$$ до $$$n$$$. Введём следующую сумму$$$^{\text{†}}$$$:

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

Рассмотрим все перестановки длины $$$n$$$ с максимальным значением $$$S(p)$$$. Необходимо вывести $$$k$$$-ю из них в лексикографическом$$$^{\text{‡}}$$$ порядке, или сообщить, что их меньше $$$k$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Например:

  • Для перестановки $$$[1, 2, 3]$$$, значение $$$S(p)$$$ равно $$$\min(1) + \min(1, 2) + \min(1, 2, 3) + \min(2) + \min(2, 3) + \min(3) =$$$ $$$1 + 1 + 1 + 2 + 2 + 3 = 10$$$.
  • Для перестановки $$$[2, 4, 1, 3]$$$ значение $$$S(p)$$$ равно $$$\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{‡}}$$$Массив $$$a$$$ лексикографически меньше массива $$$b$$$, если и только если выполняется одно из следующего:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$; или
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в массиве $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{12}$$$) — длина перестановки и номер искомой перестановки.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10 ^ 5$$$.

Выходные данные

Для каждого набора входных данных, если подходящих перестановок меньше $$$k$$$, выведите $$$-1$$$.

Иначе выведите $$$k$$$-ю подходящую перестановку.

Пример
Входные данные
6
3 2
3 3
4 11
4 6
6 39
7 34
Выходные данные
1 3 2 
2 3 1 
-1
2 4 3 1 
-1
2 3 4 5 7 6 1
Примечание

Посчитаем искомую сумму для всех перестановок длины $$$3$$$ в лексикографическом порядке:

ПерестановкаЗначение $$$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$$$

В первом наборе необходимо вывести вторую подходящую перестановку длины $$$3$$$. Посмотрев на таблицу, мы видим, что это перестановка $$$[1, 3, 2]$$$.

Во втором наборе необходимо вывести третью подходящую перестановку длины $$$3$$$. Посмотрев на таблицу, мы видим, что это перестановка $$$[2, 3, 1]$$$.