C. Запросы обновления
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующую простую задачу. Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита, а также массив индексов $$$ind$$$ длины $$$m$$$ ($$$1 \leq ind_i \leq n$$$) и строка $$$c$$$ длины $$$m$$$, состоящая из строчных букв латинского алфавита. Далее вы по порядку делали операцию обновления, а именно во время $$$i$$$-й операции вы делали $$$s_{ind_i} = c_i$$$. Обратите внимание, что вы делаете все $$$m$$$ операций от первой до последней.

Конечно же, если поменять порядок индексов в массиве $$$ind$$$ и/или порядок букв в строке $$$c$$$, можно получить разный результат. Найдите какую лексикографически наименьшую строку $$$s$$$ можно получить после $$$m$$$ операций обновления, если вы можете как угодно переставить индексы в массиве $$$ind$$$ и буквы в строке $$$c$$$.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$ тогда и только тогда, когда одно из двух условий выполнено:

  • $$$a$$$ является префиксом $$$b$$$, но $$$a \neq b$$$;
  • в первой позиции, в которой $$$a$$$ и $$$b$$$ отличаются, в строке $$$a$$$ стоит символ, который встречается в алфавите раньше, чем соответствующий символ в строке $$$b$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — длина строки $$$s$$$ и количество обновлений. Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных букв латинского алфавита.

Третья строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$ind_1, ind_2, \ldots, ind_m$$$ ($$$1 \leq ind_i \leq n$$$) — массив индексов $$$ind$$$.

Четвертая строка каждого набора входных данных содержит строку $$$c$$$ длины $$$m$$$, состоящую из строчных букв латинского алфавита.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Аналогично сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите лексикографически наименьшую строку $$$s$$$, которую можно получить, если как угодно перемешать индексы в массиве $$$ind$$$ и буквы в строке $$$c$$$.

Пример
Входные данные
4
1 2
a
1 1
cb
4 4
meow
1 2 1 4
zcwz
7 4
abacaba
1 3 5 7
damn
7 10
traktor
7 6 5 4 3 2 1 6 4 2
codeforces
Выходные данные
b
cwoz
abdcmbn
ccdeefo
Примечание

В первом наборе входных данных можно не перемешивать массив $$$ind$$$ и строку $$$c$$$ и просто сделать все операции именно в таком порядке.

Во втором наборе входных данных можно сделать массив $$$ind = [1, 1, 4, 2]$$$ и $$$c =$$$ «zczw». Тогда строка $$$s$$$ будет меняться следующим образом: $$$meow \rightarrow zeow \rightarrow ceow \rightarrow ceoz \rightarrow cwoz$$$.

В третьем наборе входных данных можно оставить массив $$$ind$$$ без изменений и сделать $$$c = $$$ «admn». Тогда строка $$$s$$$ будет меняться следующим образом: $$$abacaba \rightarrow abacaba \rightarrow abdcaba \rightarrow abdcmba \rightarrow abdcmbn$$$.