Рассмотрим следующую простую задачу. Вам дана строка \(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\).
Выходные данные
Для каждого набора входных данных выведите лексикографически наименьшую строку \(s\), которую можно получить, если как угодно перемешать индексы в массиве \(ind\) и буквы в строке \(c\).
Примечание
В первом наборе входных данных можно не перемешивать массив \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|