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

В детстве Панчо подарили перестановку$$$^{\text{∗}}$$$ $$$p_1, p_2, \ldots, p_n$$$. С этой перестановкой у него связано много тёплых воспоминаний, но в день своего $$$18$$$-летия он с ужасом понял, что некоторые элементы перестановки могли стереться.

Панчо никогда не умел хорошо запоминать длинные последовательности чисел, но он помнит два свойства перестановки:

  • Для любого $$$i$$$ ($$$1 \le i \le n-1$$$) последовательность $$$p_1, p_2, \ldots, p_i$$$ не являлась перестановкой длины $$$i$$$.
  • Для любого $$$j$$$ ($$$2 \le j \le n$$$) последовательность $$$p_j, p_{j+1}, \ldots, p_n$$$ не являлась перестановкой длины $$$n-j+1$$$.

Ваша задача — помочь Панчо, выведя перестановку, занимающую $$$k$$$-е место в лексикографическом порядке$$$^{\text{†}}$$$, соответствующую сохранившейся информации, либо сообщив, что такой перестановки не существует.

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

$$$^{\text{†}}$$$Массив $$$a$$$ лексикографически меньше массива $$$b$$$ тогда и только тогда, когда выполняется одно из следующих условий:

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

Каждый тест содержит несколько наборов входных данных. В первой строке содержится количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 100$$$). Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 10^6$$$ и $$$1 \leq k \leq 10^{18}$$$) — длина перестановки и индекс той из них, которую нужно построить.

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$p_1,p_2,\dots,p_n$$$ (если $$$p_i$$$ известно, то $$$1 \leq p_i \leq n$$$; иначе $$$p_i=-1$$$)  — известная информация об исходной перестановке.

Гарантируется, что известные значения $$$p_i$$$ (те, для которых $$$p_i \neq -1$$$) попарно различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Пример
Входные данные
4
5 1
1 2 3 4 5
6 69
-1 -1 -1 -1 -1 -1
4 2
-1 -1 -1 -1
10 10
5 3 9 -1 -1 10 -1 2 -1 -1
Выходные данные
-1
3 4 1 6 2 5 
3 1 4 2 
5 3 9 1 6 10 7 2 8 4
Примечание

В первом наборе входных данных первые два элемента известной информации равны $$$1$$$ и $$$2$$$. Поскольку эти два числа в точности образуют перестановку длины $$$2$$$, допустимых перестановок нет.

В третьем наборе входных данных существуют ровно $$$2$$$ допустимые перестановки (в лексикографическом порядке): $$$[2, 4, 1, 3]$$$ и $$$[3, 1, 4, 2]$$$.

Требуется вторая из них, поэтому она и является ответом.