Little Misha has cubes, each of which has one English lowercase letter written on it. Yesterday he laid out the cubes in two rows. In the first row Misha has
n cubes with letters, in the second -
m cubes with letters. It so happened that in these two rows there are no matching letters. In other words, no letter is contained in both rows at the same time.
Today little Misha decided to continue playing with blocks. But now he takes any one cube from any row and makes a third row of them, always adding a cube to the end. Little Misha never takes more than
k dice in a row from the same row. Misha stopped playing when he ran out of cubes in one row (in the first or in the second).
Dad, who was watching the game, noticed that playing in this way, Misha got the lexicographically smallest line. Using the known two strings, which are formed by reading the letters of the first and second rows and the number
k determine the string that little Misha received.
The string
x is lexicographically less than the string
y only and only if one of the following conditions is true:
-
x is a prefix of
y, but
x != y;
- in the first position, where
x and
y differ, in the string
x there is a letter that is in the alphabet earlier than the corresponding letter
y.
Input
The program receives several lines as input. The first line contains three numbers:
n - the number of cubes in the first row
, m - the number of cubes in the second row
, k > is an integer(1 <=
n, m, k <= 100). The second line contains a string
a of length
n - a string formed by reading the letters written on the cubes of the first row. In the third line - string
b of length
m - a string formed by reading the letters written on the cubes of the second row.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
6 4 2
aaaaaa
bbbb |
aabaabaa |