접미사 배열 복원

시간 제한1초메모리 제한512 MB

요약

순열 p가 어떤 소문자 문자열의 접미사 배열이 될 수 있는지 판정하고, 가능하면 사전순으로 가장 작은 문자열을 출력한다.

난이도: 어려움10점 중 9점
유형: 문자열, 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

길이가 $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을 출력한다.

예제3

예제 1

입력

6
2
1 2
2
2 1
3
2 3 1
6
3 4 5 1 2 6
14
3 10 2 12 14 5 13 4 1 8 6 11 7 9
7
5 1 7 4 3 2 6

예상 출력

ab
aa
bab
bcaaad
ebadcfgehagbdc
bcccadc

예제 2
입력
```
1
1
1
```
예상 출력
```
a
```
예제 3
입력
```
1
5
1 2 3 4 5
```
예상 출력
```
aaaab
```