时间限制：1秒　　内存限制：256M

---

【题目描述】

　　Farmer John 有一个长为 \(N（2≤N≤10^5）\)的排列 \(p\)，包含从 \(1\) 到 \(N\) 的每个正整数恰好一次。然而，Farmer Nhoj 闯入了 FJ 的牛棚并拆散了 \(p\)。为了不至于太过残忍，FN 写了一些能够帮助 FJ 重建 \(p\) 的提示。当 \(p\) 中剩余多于一个元素时，FN会执行以下操作：令 \(p\) 的剩余元素为 \(p_1′ ,p_2′ ,…,p_n′\)，如果 \(p_1′>p_n′\)，他写下 \(p_2′\) 并从排列中删除 \(p_1′\)。否则，他写下 \(p_{n−1}′\) 并从排列中删除 \(p_n′\) 。最终，Farmer Nhoj 将按顺序写下 \(N−1\) 个整数 \(h_1 ,h_2 ,…,h_{N−1}\) 。

　　给定 \(h\)，Farmer John 希望得到你的帮助重建与 Farmer Nhoj 的提示相一致的最小字典序 \(p\)，或者判断 Farmer Nhoj 一定犯了错误。我们知道，给定两个排列 p 和p′，如果在第一个两者不同的位置 \(i\) 处有 \(p_i <p_i′\)，则p 的字典序小于 \(p′\)。

【输入格式】

　　每个测试点包含 \(T（1≤T≤10）\) 个独立的测试用例。每个测试用例的描述如下：
　　第一行包含 \(N\)。
　　第二行包含 \(N−1\) 个整数 \(h_1 ,h_2,…,h_{N−1} （1≤h_i≤N）\)。

【输出格式】

　　输出 \(T\) 行，每个测试用例一行。如果存在与 \(h\) 相一致的 \(1..N\) 的排列 \(p\)，输出字典顺序最小的 \(p\)。如果不存在这样的 \(p\)，输出 \(−1\)。

【输入输出样例】

　Input

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

【样例解释】

　　对于第四个测试用例，如果 \(p=[3,1,2,4]\) 则 FN 将写下 \(h=[2,1,1]\)。
　　\(p' = [3,1,2,4]\)
　　\(p_1' < p_n' -> h_1 = 2\)
　　\(p' = [3,1,2]\)
　　\(p_1' > p_n' -> h_2 = 1\)
　　\(p' = [1,2]\)
　　\(p_1' < p_n' -> h_3 = 1\)
　　\(p' = [1]\)
　　注意排列 \(p=[4,2,1,3]\) 也会产生同样的 \(h\)，但 \([3,1,2,4]\) 字典序更小。
　　对于第二个测试用例，不存在与 \(h\) 相一致的 \(p\)；\(p=[1,2]\) 和 \(p=[2,1]\) 均会产生 \(h=[1]\)，并非 \(h=[2]\)。

　Output

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

【测试点性质】

　　测试点 2：N≤8。
　　测试点 3−6：N≤100。
　　测试点 7−11：没有额外限制。

【来源】

　　Mr.he