题目描述

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 \neq j$，有 $p_i \neq p_j$。

保证所有测试数据中 $n$ 的总和不超过 $1000$。

输出格式

对于每组测试数据，输出 $n$ 个正整数，表示字典序最小的神秘排列。如果不存在这样的排列，输出 $-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]$。

由 ChatGPT 4.1 翻译

样例

4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1

2 3 1
1 2 3 4 5
1 2 4 3
-1