- Time limit: 1.00 s
- Memory limit: 512 MB
There is an 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 th word in the list?
Input
The first input line has two integers and : the size of the grid and the parameter .
After this, there are lines that describe the grid. Each line consists of 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
].