P15075 [ICPC 2024 Chengdu R] Closest Derangement

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 < b$ if and only if at the smallest index $i$ where $a_i \neq b_i$, it holds that $a_i < b_i$.

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

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

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.