Условие недоступно на русском языке
G. 互异排列—扩展
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一个 1 到 n 的排列 p，小 H 需要将数字 n + 1 插入到 p 的某个位置（包括开头和结尾），得到一个新的排列 q（长度为 n + 1）。他希望新排列 q 的所有前缀和对 (n + 1) 取模的结果 互不相同 。

形式化地，定义前缀和数组 S，其中 ，对于 k = 1, 2, ..., n + 1。要求 S1, S2, ..., Sn + 1 这 n + 1 个值互不相同。

请你帮助小 H 判断是否存在这样的插入位置，如果存在，输出任意一个可行的排列 q，否则输出  - 1 。

Input

第一行一个整数 T（1 ≤ T ≤ 1000），表示测试用例数量。

每个测试用例包含两行：

  • 第一行一个整数 n（1 ≤ n ≤ 106）
  • 第二行 n 个整数 p1, p2, ..., pn，表示原排列 p

保证所有测试用例的 n 之和不超过 106。

Output

对于每个测试用例：

  • 如果存在满足条件的插入位置，输出一行 n + 1 个整数表示排列 q（多个答案输出任意一个）。
  • 否则输出一行  - 1。
Example
Input
2
1
1
2
2 1
Output
2 1
-1