Monocarp 是一个住在 Byteland 的小男孩,他喜欢编程。
最近,他发现了一个长度为$$$n$$$的排列。他必须想出一个神秘的排列。它必须是一种新的排列,并且每个位置都与旧的排列不同。
更正式地说,如果旧排列是 $$$p_1,p_2,\ldots,p_n$$$ 而新排列是 $$$q_1,q_2,\ldots,q_n$$$ 则必须满足 $$$$$$p_1\neq q_1, p_2\neq q_2, \ldots ,p_n\neq q_n.$$$$$$
Monocarp 害怕字典顺序上的大排列。你能帮他找到字典顺序上最小的神秘排列吗?
输入
输入数据中有多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 200$$$) — 测试用例的数量。接下来是测试用例描述。
每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$1\leq n\leq 1000$$$) — 排列的长度。
每个测试用例的第二行包含 $$$n$$$ 不同的正整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$)。保证 $$$p$$$ 是一个排列,i。 e. $$$p_i \neq p_j$$$ 对于所有 $$$i \neq j$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,输出 $$$n$$$ 正整数 - 按字典顺序排列的最小神秘排列。如果这样的排列不存在,则输出$$$-1$$$。
示例
输入 #1
4 3 1 2 3 5 2 3 4 5 1 4 2 3 1 4 1 1
输出 #1
2 3 1 1 2 3 4 5 1 2 4 3 -1
注意
在第一个测试用例中,可能的神秘排列是 $$$[2,3,1]$$$ 和 $$$[3,1,2]$$$。按字典顺序,两者中较小的是 $$$[2,3,1]$$$。
在第二个测试用例中,$$$[1,2,3,4,5]$$$ 是字典顺序上最小的排列,而且它也是神秘的。
在第三个测试用例中,可能的神秘排列是 $$$[1,2,4,3]$$$, $$$[1,4,2,3]$$$, $$$[1,4,3,2]$$$, $$$[3,1,4,2]$$$, $$$[3,2,4,1]$$$, $$$[3,4,2,1]$$$、$$$[4,1,2,3]$$$、$$$[4,1,3,2]$$$ 和 $$$[4,3,2,1]$$$。最小的是$$$[1,2,4,3]$$$。