Перетворення суфиксів
Задано текст 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.