eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Указ рассудительного вождя

Указ рассудительного вождя

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Недавно вождю племени Йавгустабэ, члены которого называют себя Йавгустохутораци, Рассудительному Манулу подарили удивительное устройство - печатную машинку. Манул рассудительно отдал её своему писарю, юному индейцу Кривому Перу, дабы индейцы племени Йавгустабэ наконец смогли без труда разобрать, что же именно написано Кривым Пером в указах вождя.

Печатная машинка оказалась устройством непростым. Она имеет 26 клавиш для ввода каждой из маленьких латинских букв. Клавиши расположены в три ряда: 10 клавиш в первом ряду, 9 клавиш во втором и 7 - в третьем. В каждом ряду клавиши нумеруются слева направо, начиная с единицы. Более того, клавиши расположены таким образом, что каждая клавиша расположена строго над клавишей следующего ряда, имеющей такой же номер в своём ряду. На машинке нет клавиш для ввода символов, отличных от маленьких латинских букв, в том числе нет клавиш для ввода пробельных символов, поэтому все слова указа на машинке Кривому Перу придётся печатать слитно.

Первое время, печатая, Кривое Перо часто промахивался мимо нужной клавиши и нажимал вместо неё одну из клавиш, соседних с ней сверху, снизу, слева, справа, справа-сверху, справа-снизу, слева сверху, слева-снизу.

Кроме того, Кривое Перо не смог разобраться с порядком ввода букв, поэтому вводит буквы фразы в произвольном порядке. Например, вместо фразы "helloworld" Кривое Перо может набрать фразу "oldhellrow" (если, конечно, ни разу не промахнётся мимо нужной клавиши).

И вот однажды наступил день, когда впервые указ вождя был написан Кривым Пером не пером, а на печатной машинке. Естественно, с ошибками и произвольным порядком букв во всём указе. Помогите Йавгустохуторацам узнать, что же хотел сказать рассудительный вождь. При этом нужно учитывать следующее. Во-первых, вождь рассудительно распорядился, чтобы Кривое Перо печатал указ под присмотром шамана Острого Глаза, благодаря наблюдательности которого Кривое Перо наверняка промахнулся мимо нужной клавиши во время написания указа не более N раз (при этом буквы всё же были набраны в произвольном порядке). Во-вторых, после того, как Рассудительный Манул однажды побывал в качестве почётного гостя на одном ритуале шаманов племени Тарскийа, он очень заинтересовался священным для того племени лексикографическим порядком и стал стараться диктовать указы так, чтобы они были как можно меньше в лексикографическом порядке. В связи с этим жители хотят, зная указ, узнать лексикографически минимальную строку из тех, которые могли быть в указе вождя.

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

В первых трёх строках входного файла задано расположение клавиш печатной машинки - три строки, содержащие маленькие латинские буквы, длины 10, 9 и 7 символов соответственно. В четвёртой строке содержится текст указа вождя, набранный Кривым Пером и потому содержащий ошибки - непустая строка, состоящая только из маленьких латинских букв, длина которой не превосходит 5·10^4. В пятой строке записано число N (0N5·10^4) - максимальное число букв, неверно набранных Кривым Пером.

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

Выведите лексикографически минимальную строку, которая могла быть указом Рассудительного вождя.

Пример

Входные данные #1
qwertyuiop
asdfghjkl
zxcvbnm
qwerty
2
Выходные данные #1
aaerty