Задача №115385. Отгадай строку
Вася решил сыграть с вами в игру. Он загадывает строку, состоящую из первых \(k\) строчных букв латинского алфавита, после чего выписывает все её непустые суффиксы и сортирует их в лексикографическом\(^{\dagger}\) порядке. Далее он сообщает вам получившийся порядок суффиксов, где суффиксу соответствует позиция в строке, с которой он начинается. Также он сообщает вам, сколько каждой буквы было в исходной строке.
Ваша задача состоит в том, чтобы отгадать загаданную строку.
\(^{\dagger}\)Строка \(s\) лексикографически меньше, чем строка \(t\), если есть индекс \(i\) такой, что \(s_i < t_i\) (в алфавитном порядке), и \(s_j = t_j\) для всех \(j < i\). Иными словами, для первого такого индекса \(i\), где строки различны, \(s_i < t_i\). Если такого индекса не существует, то лексикографически меньшей считается строка меньшей длины.
Каждый тест состоит из нескольких наборов входных данных. В первой строке дано целое число \(t\), \((1 \le t \le 10\,000)\) — количество наборов входных данных. Далее даны \(t\) наборов входных данных друг за другом, в следующем формате:
В первой строке дано два целых числа \(n, k\) \((1 \le n \le 200\,000, 1 \le k \le 26)\) — размер строки и количество различных букв в строке. Гарантируется, что загаданная строка содержит только первые \(k\) букв латинского алфавита.
Во второй строке дано n целых положительных чисел \(a_i\) \((1 \le a_i \le n)\) — индексы суффиксов в порядке после лексикографической сортировки. Гарантируется, что индекс каждого суффикса встречается ровно один раз.
В третьей строке дано \(k\) целых \(c_1, c_2, \ldots c_k\) \((0 \le c_i \le n)\) — количество букв \(a\) в строке, количество букв \(b\) в строке и так далее в алфавитном порядке.
Гарантируется, что \(c_1 + c_2 + \ldots + c_k = n\).
Гарантируется, что сумма \(n\) по всем тестам не превышает \(200\,000\).
Выведите строку, которую загадал Вася. Гарантируется, что существует ровно одна строка, которая удовлетворяет данным условиям.
4 4 3 3 1 4 2 2 1 1 3 2 3 2 1 1 2 1 1 1 1 10 2 1 3 8 5 10 2 7 4 9 6 4 6
acab bba a abababbabb