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 kth 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

• 1 \le n \le 30

Example

Input:

3 2
AYB
ABT
UAY

Output:

AABTY

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