#P18208. Closest Derangement

Closest Derangement

Closest Derangement

Blackbird 有一个长度为 nn 的排列 pp。他想找一个 pp 的错位排列 qq:qq 也是长度为 nn 的排列,且对于每个 1≤i≤n1\le i\le n,都有 qi≠piq_i\ne p_i。

同时,他希望

∑i=1n∣pi−qi∣\sum_{i=1}^n|p_i-q_i|

尽可能小。达到这一最小值的排列 qq 称为 pp 的最近错位排列。

最近错位排列可能不唯一。请输出其中字典序第 kk 小的排列;如果最近错位排列不足 kk 个,输出 −1-1。

长度为 nn 的排列是由 11 到 nn 这 nn 个不同正整数组成的序列。对于两个不同的排列 a,ba,b,在它们第一个不同的位置 ii 上,若 ai<bia_i<b_i,则 aa 的字典序小于 bb。

输入格式

第一行包含一个整数 TT,表示测试用例数量。

每个测试用例的第一行包含两个整数 n,kn,k。

第二行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,表示排列 pp。

输出格式

对于每个测试用例,若最近错位排列不足 kk 个,输出一行 −1-1。

否则,输出一行 nn 个以空格分隔的正整数,表示字典序第 kk 小的最近错位排列 qq。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • 2≤n≤2×1052\le n\le2\times10^5;
  • 1≤k≤1091\le k\le10^9;
  • pp 是一个 11 到 nn 的排列;
  • 所有测试用例的 nn 之和不超过 10610^6。

样例

输入:

2
2 2
2 1
3 2
1 2 3

输出:

-1
3 1 2

解释:

  • 第一个测试用例只有一个最近错位排列 [1,2][1,2],所以不存在第 22 个。
  • 第二个测试用例的最近错位排列为 [2,3,1][2,3,1] 和 [3,1,2][3,1,2]。后者的字典序更大,因此是第 22 小。