Преобразование суффиксов
Задан текст s[1..n] длины n. Создадим суффиксный массив, взяв все его суффиксы
s[1..n], s[2..n], ..., s[n..n]
и отсортировав их лексикографически. Получим отсортированный список суффиксов:
s[p(1)..n], s[p(2)..n], ..., s[p(n)..n]
и назовем последовательность p(1), p(2), ..., p(n) суффиксным массивом s[1..n]. Например, если s = abbaabab, то отсортированный список суффиксов имеет вид:
aabab, ab, abab, abbaabab, b, baabab, bab, bbaabab
и суффиксный массив выглядит так: 4, 7, 5, 1, 8, 3, 6, 2.
Оказывается, построить такой массив можно за линейное время. Ваша задача будет полностью противоположной: по заданным p(1), p(2), p(3), ..., p(n) следует проверить, существует ли хотя бы один текст из прописных букв английского алфавита, для которого заданная последовательность будет суффиксным массивом. Если ответ положительный, то вывести любой такой текст. Иначе вывести -1.
Входные данные
Входные данные состоят из нескольких описаний суффиксных массивов. Первая строка содержит количество тестов t (t ≤ 100). Каждое описание начинается со строки, содержащей длину текста и массива n (1 ≤ n ≤ 500000). Следующая строка содержит целые числа p(1), p(2), ..., p(n). Считайте, что 1 ≤ p(i) ≤ n и ни одно из значений p(i) не встречается дважды. Размер входных данных не превышает 50 MB.
Выходные данные
Для каждого теста вывести любой текст, удовлетворяющий заданному суффиксному массиву. Если требуемого текста из прописных букв английского алфавита не существует, то вывести -1.