You have a table with N rows and M columns. Each cell of the table contains one lowercase letter of the English alphabet. Consider all possible paths from the upper left corner to the lower right corner, if you are only allowed to go to the right and down. The concatenation of letters in traversal order makes up a string. Let's say that this string is a path value. Now consider all such paths and sort their values in alphabetical order. Your task is to find the value of the Kth path in this sorted list.
Input
The first line contains two integers N - the number of rows and M - the number of columns of the given table (1 ≤ N, M ≤ 30). Each of the following N lines contains exactly M lowercase letters of the English alphabet. The last line of the input file contains an integer K (1 ≤ K ≤10
18). It is guaranteed that for K the answer always exists.
Imprint
The first and last line of the output file must contain one line - the answer to the problem.
Explanations for example
aefdgk, aefdgk, aefdjk, aefijk, aehijk
Examples
| # |
Input |
Output |
| 1 |
3 4
abcd
efdg
hijk
4 |
abfdgk |