## Intermediate Words

Let L(*W*

_{1},

*W*

_{2}) denote the Levenshtein distance between words

*W*

_{1}and

*W*

_{2}over an alphabet Σ. We say that a word

*W*over Σ is

*intermediate*with respect to

*W*

_{1},

*W*

_{2}and a threshold distance

*D*if and only if L(

*W*,

*W*

_{1}) ≤

*D*and L(

*W*,

*W*

_{2}) ≤

*D*.

### The task

For two words over a finite alphabet and a threshold distance, find the shortest intermediate word.

### Input

The first line contains a single string specifying a finite alphabet Σ. The alphabet is a subset of small English
letters {'a', 'b', ..., 'z'}. The characters of the string are sorted in ascending order.
The second line contains integer *D* which represents the threshold distance.
The third input line contains a non-empty string which represents a word *W*_{1} over Σ.
Similarly, the fourth input line contains a non-empty string which represents a word *W*_{2} over Σ.
It holds |*W*_{1}|, |*W*_{2}| ≤ 50 and 1 ≤ *D* ≤ 15.

### Output

The output is one line containing the shortest string *S* over Σ fulfilling
L(*S*,*W*_{1}), L(*S*,*W*_{2}) ≤ *D*.
If there are more such shortest strings, then *S* is the first one in lexicographical order among them.
It is guaranteed that the output string *S* is always non-empty.

### Example 1

**Input**

abcd 3 aaaabbaaacd baaabcbaa

**Output**

aaaabaaa

### Example 2

**Input**

cde 5 deecded cce

**Output**

cd

### Example 3

**Input**

cd 8 dccccddcccdd dccccccd

**Output**

cccc

### Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

**Link to public data set**