長さ $n$ の文字列 $s$ に対して、$j = 1, \dots, n$ のすべてについて、$s[x \dots j]$ が $s[1 \dots j]$ の最小の接尾辞（suffix）であるとき、$p_j = x$ と定義します。 （ある文字列の接尾辞が、その文字列の他のどの接尾辞よりも辞書順で小さい場合、それを最小の接尾辞と呼びます。）

$p_1, \dots, p_n$ から $s$ を復元してください。もし複数の答えが存在する場合は、辞書順で最小のものを求めてください。

入力

最初の行にはテストケースの数 $T$ ($1 \le T \le 10^5$) が含まれます。 各テストケースにおいて、最初の行には $s$ の長さを表す整数 $n$ ($1 \le n \le 3 \times 10^6$) が含まれます。次の行には $n$ 個の整数 $p_1, \dots, p_n$ ($1 \le p_i \le i$、すべての $1 \le i \le n$ に対して) が含まれます。 すべてのテストケースにおける $n$ の総和は $3 \times 10^6$ を超えないことが保証されています。

出力

各テストケースについて、1行で出力してください。解が存在しない場合は $-1$ を出力してください。それ以外の場合は、辞書順で最小の $s$ を出力してください。$s$ の各文字は正の整数で表されます。整数が小さいほど、辞書順で小さい文字であることを意味します。

入出力例

入力 1

6
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3

出力 1

1 2 2
-1
1 2 1
1 1 2
2 1 2
1 1 1

注記

入出力が非常に大きくなる可能性があるため、高速な入出力手法を使用することを推奨します。