對於一個長度為 $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

說明

由於輸入/輸出量可能非常大，建議使用快速輸入/輸出方法。