Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
Pancho was given a permutation$$$^{\text{∗}}$$$ $$$p_1, p_2, \ldots, p_n$$$ as a gift when he was a child. He made many fond memories with his permutation, but the day he turned $$$18$$$, he realized to his horror that some of the elements of the permutation may have been erased.
Pancho was never great at remembering long sequences of numbers, but he recalls two of its properties:
For any $$$i$$$ ($$$1 \le i \le n-1$$$), $$$p_1, p_2, \ldots, p_i$$$ was not a permutation of length $$$i$$$.
For any $$$j$$$ ($$$2 \le j \le n$$$), $$$p_j, p_{j+1}, \ldots, p_n$$$ was not a permutation of length $$$n-j+1$$$.
Your task is to help Pancho by outputting the $$$k$$$-th smallest permutation in lexicographical order$$$^{\text{†}}$$$ that matches the information he remembers or reporting that there is no such permutation.
$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).
$$$^{\text{†}}$$$An array $$$a$$$ is lexicographically smaller than an array $$$b$$$ if and only if one of the following holds:
$$$a$$$ is a prefix of $$$b$$$, but $$$a \neq b$$$; or
in the first position where $$$a$$$ and $$$b$$$ differ, the array $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.
Input
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 100$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^6$$$ and $$$1 \leq k \leq 10^{18}$$$) — the length of the permutation and the index of the one you must construct.
The second line of each test case contains $$$n$$$ integers $$$p_1,p_2,\dots,p_n$$$ (if $$$p_i$$$ is known, then $$$1 \leq p_i \leq n$$$; otherwise, $$$p_i=-1$$$) — the information provided about the original permutation.
It is guaranteed that the known values $$$p_i$$$ (those with $$$p_i \neq -1$$$) are pairwise distinct.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
Output
Print a line for each test case. Print $$$-1$$$ if there are fewer than $$$k$$$ valid permutations. Otherwise, print $$$n$$$ integers representing the requested permutation.
Example
Input
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
Output
-1
3 4 1 6 2 5
3 1 4 2
5 3 9 1 6 10 7 2 8 4
Note
In the first test case, the first two elements of the given information are $$$1$$$ and $$$2$$$. Since these two numbers are precisely the elements of a permutation of length $$$2$$$, there are no valid permutations.
In the third test case, there are exactly $$$2$$$ valid permutations (listed in lexicographical order), $$$[2, 4, 1, 3]$$$ and $$$[3, 1, 4, 2]$$$.
Visitar URL original
