問題文

(1,2,\dots,M) の順列 Q=(Q_1,Q_2,\dots,Q_M) に対し、長さ M-1 の数列 f(Q) を以下のように定めます。

• 長さ M-1 の数列 X を X=(0,0,\dots,0) で初期化する
• 以下の操作を M-1 回行う
  • i=1,2,\dots,M-1 の順に以下を行う
    • Q_i > Q_{i+1} ならば Q_i と Q_{i+1} を入れ替え、X_i に 1 を加える
    • Q_i < Q_{i+1} ならば何もしない
• 最終的な X を f(Q) とする

長さ N-1 の数列 B=(B_1,B_2,\dots,B_{N-1}) が与えられます。(1,2,\dots,N) の順列 P であって f(P)=B を満たすものが存在するか判定し、存在するならばそのようなもののうち辞書順で最小のものを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 1.5 \times 10^5
• 2 \leq N \leq 3 \times 10^5
• 0 \leq B_i \leq N-1
• 入力は全て整数
• 1 つの入力ファイルに含まれる N の総和は 3 \times 10^5 以下

入力例 1

3
4
2 1 1
5
2 0 2 4
6
2 3 2 1 1

出力例 1

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

1 つ目のテストケースについて P=(3,2,4,1) のとき f(P) は次のように計算されます。

• はじめ X=(0,0,0) である
• 1 回目の操作は次のように行われる
  • P_1 > P_2 なので X_1 に 1 を加算し、P_1 と P_2 を入れ替える
    • X=(1,0,0),P=(2,3,4,1) となる
  • P_2 < P_3 なので何もしない
  • P_3 > P_4 なので X_3 に 1 を加算し、P_3 と P_4 を入れ替える
    • X=(1,0,1),P=(2,3,1,4) となる
• 2 回目の操作は次のように行われる
  • P_1 < P_2 なので何もしない
  • P_2 > P_3 なので X_2 に 1 を加算し、P_2 と P_3 を入れ替える
    • X=(1,1,1),P=(2,1,3,4) となる
  • P_3 < P_4 なので何もしない
• 3 回目の操作は次のように行われる
  • P_1 > P_2 なので X_1 に 1 を加算し、P_1 と P_2 を入れ替える
    • X=(2,1,1),P=(1,2,3,4) となる
  • P_2 < P_3 なので何もしない
  • P_3 < P_4 なので何もしない

よって f(P) = (2,1,1) となります。特にこの P が f(P)=B を満たす P のうち辞書順最小のものです。

2 つ目のテストケースについて f(P)=(2,0,2,4) となる順列 P は存在しません。