F. Pancho's Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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]$$$.

The answer is the second one, as requested.