Задача
У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши
n кубиков с буквами, во втором -
m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более
k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу
k определите строку, которую получил маленький Миша.
Строка
x лексикографически меньше строки
y только и только тогда, когда выполняется одно из следующих условий:
-
x является префиксом
y, но
x != y;
- в первой позиции, где
x и
y различаются, в строке
x находится буква, которая стоит в алфавите раньше, чем соответствующая буква
y.
Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа:
n - количество кубиков в первом ряду
, m - количество кубиков во втором ряду
, k - целое число(1 <=
n, m, k <= 100). Во второй строке записана строка
a длиной
n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка
b длиной
m - строка, образованная прочтением букв, написанных на кубиках второго ряда.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 4 2
aaaaaa
bbbb |
aabaabaa |