Intermediate Words

Let L(W₁, W₂) denote the Levenshtein distance between words W₁ and W₂ over an alphabet Σ. We say that a word W over Σ is intermediate with respect to W₁, W₂ and a threshold distance D if and only if L(W, W₁) ≤ D and L(W, W₂) ≤ 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₁ over Σ. Similarly, the fourth input line contains a non-empty string which represents a word W₂ over Σ. It holds |W₁|, |W₂| ≤ 50 and 1 ≤ D ≤ 15.

Output

The output is one line containing the shortest string S over Σ fulfilling L(S,W₁), L(S,W₂) ≤ 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