길이가 $n$인 문자열 $s$에 대하여, 모든 $j = 1, \dots, n$에 대해 $s[x \dots j]$가 $s[1 \dots j]$의 최소 접미사(minimum suffix)라면 $p_j = x$라고 정의합니다. (어떤 문자열의 접미사가 그 문자열의 다른 모든 접미사보다 사전순으로 작을 때, 이를 최소 접미사라고 합니다.)

$p_1, \dots, p_n$이 주어졌을 때 $s$를 복원해야 합니다. 가능한 답이 여러 개라면, 사전순으로 가장 작은 것을 찾으십시오.

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10^5$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 $s$의 길이를 나타내는 정수 $n$ ($1 \le n \le 3 \times 10^6$)이 주어집니다. 다음 줄에는 $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

참고

입력과 출력이 매우 클 수 있으므로, 빠른 입출력 방식을 사용하는 것을 권장합니다.