D. Closest Derangement
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Blackbird has a permutation $$$p$$$ of length $$$n$$$. He wants to find a derangement $$$q$$$ of $$$p$$$, which means $$$q$$$ is another permutation of length $$$n$$$ satisfying $$$q_i\neq p_i$$$ for each $$$i=1,2,\ldots,n$$$. At the same time, $$$\sum_{i=1}^{n}|p_i-q_i|$$$ should be minimized. A permutation $$$q$$$ that satisfies the above conditions is called the closest derangement of $$$p$$$.

There may be multiple closest derangements of $$$p$$$, and your task is to output the $$$k$$$-th smallest closest derangement in lexicographical order. If there are fewer than $$$k$$$ closest derangements of $$$p$$$, output $$$-1$$$.

A permutation of length $$$n$$$ refers to a sequence of length $$$n$$$ where all elements are distinct and are positive integers from $$$1$$$ to $$$n$$$. Permutations can be sorted in lexicographical order. Let $$$a$$$ and $$$b$$$ be two distinct permutations of length $$$n$$$. Then, $$$a \lt b$$$ if and only if at the smallest index $$$i$$$ where $$$a_i \neq b_i$$$, it holds that $$$a_i \lt b_i$$$.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 10^4$$$), representing the number of test cases.

For each test case, the first line contains two positive integers $$$n$$$ ($$$2\le n \le 2 \cdot 10^5$$$) and $$$k$$$ ($$$1\le k \le 10^9$$$). The second line contains $$$n$$$ positive integers $$$p_1, p_2, \ldots, p_n$$$, representing the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, if there are at least $$$k$$$ closest derangements, output $$$n$$$ positive integers $$$q_1, q_2, \ldots, q_n$$$ in a single line separated by spaces, representing the $$$k$$$-th smallest closest derangement of $$$p$$$ in lexicographical order. Otherwise, output $$$-1$$$.

Example
Input
2
2 2
2 1
3 2
1 2 3
Output
-1
3 1 2
Note

For the first test case, $$$[1,2]$$$ is the only closest derangement, so output $$$-1$$$.

For the second test case, $$$[2,3,1]$$$ and $$$[3,1,2]$$$ are closest derangements of $$$p$$$, and $$$[3,1,2]$$$ is larger than $$$[2,3,1]$$$ in lexicographical order.