접미사 배열 복원

길이가 $n$인 문자열 $s[1..n]$의 모든 접미사

$s[1..n],\ s[2..n],\ \ldots,\ s[n..n]$

를 사전순으로 정렬하면 다음과 같은 정렬된 목록을 얻는다.

$s[p(1)..n],\ s[p(2)..n],\ \ldots,\ s[p(n)..n]$

이때 수열 $p(1), p(2), \ldots, p(n)$을 문자열 $s$의 접미사 배열이라고 한다. 예를 들어 $s = \texttt{abbaabab}$이면 모든 접미사를 사전순으로 정렬한 결과는

aabab, ab, abab, abbaabab, b, baabab, bab, bbaabab

이고, 따라서 접미사 배열은 $4, 7, 5, 1, 8, 3, 6, 2$이다.

이 문제에서 풀어야 하는 것은 그 반대이다. 수열 $p(1), p(2), \ldots, p(n)$($1$부터 $n$까지의 순열)이 주어질 때, 이 수열을 접미사 배열로 가지는 소문자 알파벳 문자열이 존재하는지 판별하고, 존재한다면 그러한 문자열을 복원하라.

첫째 줄에 테스트 케이스의 개수 $t$($1 \le t \le 100$)가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 문자열과 배열의 길이 $n$($1 \le n \le 500000$)이 주어지고, 둘째 줄에는 $n$개의 정수 $p(1), p(2), \ldots, p(n)$이 주어진다. 모든 $i$에 대해 $1 \le p(i) \le n$이고 같은 값이 두 번 나타나지 않음이 보장된다(즉 $p$는 순열이다). 전체 입력의 크기는 50MB를 넘지 않는다.

각 테스트 케이스마다, 주어진 수열을 접미사 배열로 가지는 소문자 알파벳(a–z) 문자열이 존재하면 그중 사전순으로 가장 작은 문자열을 한 줄에 출력한다. 그러한 문자열이 존재하지 않으면 -1을 출력한다.