시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB186571.429%

문제

Suppose you have a table of N rows and M columns. Each cell of the table contains a single lowercase english letter. Consider any path from the top-left to the bottom-right cell of the table, if you are only allowed to move right and down. Letters in the cells met along the path form a string. This string is said to be the value of the path. Now consider all such possible paths and sort them by their values in alphabetical order. Your task is to find the value of the K-th path in this sorted list.

입력

The first line of the input file contains two integer numbers N — the number of rows and M — the number of columns of the given table (1 ≤ N, M ≤ 30). Each of the next N lines contains exactly M lowercase english letters. The last line of the input file contains a single integer K (1 ≤ K ≤ 1018). It is guaranteed that the answer exists for the given K.

출력

The first and only line of the output file must contain a single string – the answer to the problem.

예제 입력 1

3 4
abcd
efdg
hijk
4

예제 출력 1

abfdgk

출처

Olympiad > International Zhautykov Olympiad > IZhO 2011 H번

  • 스페셜 저지를 만든 사람: yclock