$1\sim n$ の順列 $p$ が与えられます。

次の条件を満たす長さ $n$ の列 $a$ を構築してください。

• 列 $a$ の各要素は $n$ 以下の正整数である。
• $1 \le l \le r \le n$ かつ $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$ を満たす整数の順序対 $(l,r)$ が存在しない。

または、解が存在しないことを報告してください。

ここで、$1\sim n$ の順列とは、$n$ 以下のすべての正整数がちょうど一度ずつ現れる列です。

入力

この問題には複数のテストケースがあります。

最初の行には、テストケース数を表す整数 $T$ が与えられます。

続いて、各テストケースが順に与えられます。各テストケースについて：

• 最初の行には整数 $n$ が与えられます。
• 次の行には、与えられる順列 $p$ を表す $n$ 個の整数が与えられます。

出力

各テストケースについて、次のように一行で出力してください。

• 条件を満たす列 $a$ が存在する場合、構築した列 $a$ を表す $n$ 個の整数を空白区切りで出力してください。
• 条件を満たす列 $a$ が存在しない場合、$-1$ を出力してください。

条件を満たす出力はすべて正解とみなされます。

入出力例

入力 1

4
3
3 2 1
2
1 2
5
4 2 1 5 3
7
5 7 3 1 2 4 6

出力 1

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

注記

第 $1$ テストケースでは、$\{1,3,3\}$ と $\{1,1,3\}$ はいずれも条件を満たす列 $a$ です。

第 $2$ テストケースでは、条件を満たす列 $a$ が存在しないことを証明できます。

第 $3$ テストケースでは、$\{5,3,2,1,1 \}$ のほか、$\{3,4,5,3,2 \}$、$\{1,4,5,3,4 \}$、$\{5,3,3,4,5\}$ なども条件を満たす列 $a$ です。

制約

$\sum n$ は、一つのテストファイル内の $n$ の総和を表します。

すべてのデータについて、$1 \le T \le 5000$，$2 \le n \le 10^6$，$\sum n \le 10^6$ であり、$p$ は $1\sim n$ の順列であることが保証されます。