Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Find a Word

Find a Word

Time limit:1.00 s
Memory limit:512 MB

There is an $n \times n$ grid whose each square contains a character between A and Z. You can create a word by starting at the upper-left square and moving one step right or down on each step until you reach the lower-right square.

If you create a list of all such words and sort them lexicographically, what is the $k$th word in the list?

Input

The first input line has two integers $n$ and $k$: the size of the grid and the parameter $k$.

After this, there are $n$ lines that describe the grid. Each line consists of $n$ characters between A and Z.

Output

Print the requested word. You can assume that such a word exists.

Constraints
Example

Input:
3 2
AYB
ABT
UAY


Output:
AABTY

Explanation: The list is [AABAY, AABTY, AAUAY, AYBAY, AYBTY, AYBTY].