Koishi 给了你一个长度为 $n$ 的整数数组 $B$，满足 $1 \le B_1 \le B_2 \le \dots \le B_n \le n + 1$。

令 $S(T)$ 表示数组 $T$ 中出现的数字集合。Koishi 问你是否存在一个长度为 $n$ 的数组 $A$，使得对于任意 $1 \le l \le r \le n$，等式 $S(A[l, r]) = S(A[1, n])$ 成立当且仅当 $r \ge B_l$。如果存在，请构造一个满足上述条件的数组 $A$。

这里，$A[l, r]$ 表示由 $A_l, A_{l+1}, \dots, A_r$ 组成的 $A$ 的子数组。

你只能在数组中使用 $0$ 到 $10^9$ 之间的整数。可以证明，如果存在解，则一定存在满足此条件的解。

注意：如果存在索引 $i$ ($1 \le i \le n$) 使得 $B_i < i$ 成立，则所需的 $A$ 一定不存在。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 6 \cdot 10^4$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示数组 $B$（以及 $A$）的长度。

下一行包含 $n$ 个整数 $B_1, B_2, \dots, B_n$ ($1 \le B_1 \le B_2 \le \dots \le B_n \le n + 1$)，即 Koishi 给你的数组。

保证 $\sum n \le 2.6 \cdot 10^6$。

输出格式

对于每个测试用例，输出一行。如果这样的数组 $A$ 不存在，输出 $-1$。否则，输出 $n$ 个数字：即由 $0$ 到 $10^9$ 范围内的整数组成的数组 $A$。如果有多种可能的解，输出其中任意一个即可。

样例

输入 1

3
4
3 3 5 5
7
4 6 6 7 8 8 8
5
2 3 4 4 6

输出 1

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