对于一个长度为 $n$ 的字符串 $s$，我们定义 $p_j = x$，其中 $s[x \dots j]$ 是 $s[1 \dots j]$ 的最小后缀，对于所有 $j = 1, \dots, n$ 均成立。（如果一个后缀在字典序上小于该字符串的所有其他后缀，则称其为该字符串的最小后缀。）

你需要根据 $p_1, \dots, p_n$ 还原字符串 $s$。如果存在多个答案，请找出字典序最小的一个。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 3 \times 10^6$)，表示 $s$ 的长度。下一行包含 $n$ 个整数 $p_1, \dots, p_n$ ($1 \le p_i \le i$，对于所有 $1 \le i \le n$)。

保证所有测试用例的 $n$ 之和不超过 $3 \times 10^6$。

输出格式

对于每个测试用例，输出一行。如果没有解，输出 $-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

说明

由于输入/输出数据量可能很大，建议使用快速输入/输出方法。