Кузнецов любит искусство, поэзию и музыку. И строки, состоящие из строчных латинских букв.
Недавно Кузнецов нашел две строки \(a\) и \(b\) длины \(n\) и \(m\) соответственно. Они состоят из строчных английских букв и ни один символ не содержится одновременно в обеих строках.
Пусть еще одна строка \(c\) изначально пуста. Кузнецов может делать следующие два типа операций:
- Выбрать любой символ из строки \(a\), удалить его из строки \(a\) и добавить в конец строки \(c\).
- Выбрать любой символ из строки \(b\), удалить его из строки \(b\) и добавить в конец строки \(c\).
Однако Кузнецов не может сделать более \(k\) операций одного типа подряд. Кузнецов должен выполнять операции до того момента, как строка \(a\) либо строка \(b\) станет пустой. Какое лексикографически наименьшее значение \(c\) возможное после того, как Кузнецов закончит выполнение операций?
Строка \(x\) лексикографически меньше строки \(y\) тогда и только тогда, когда выполняется одно из следующих условий:
- \(x\) является префиксом \(y\), но \(x \neq y\);
- в первой позиции, где \(x\) и \(y\) различаются, в строке \(x\) находится буква, которая стоит в алфавите раньше, чем соответствующая буква в \(y\).
Выходные данные
Для каждого набора входных данных выведите одну строку \(c\) — ответ на задачу.
Примечание
В первом наборе входных данных оптимально взять две буквы «a» из строки \(a\) и добавить их к строке \(c\). Теперь запрещается выполнять операцию со строкой \(a\), следовательно, необходимо взять один символ «b» из строки \(b\). Следуя этой логике, мы получаем, что \(c\) становится «aabaabaa» в момент, когда строка \(a\) становится пуста.
Во втором наборе входных данных оптимально взять как можно больше «a» из строки \(a\), а затем взять как можно больше «b» из строки \(b\). В конце мы берем два символа «c» из строки \(a\), делая ее пустой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy
|
aabaabaa
aaabbcc
dihktlwlxnyoz
|