#!/usr/bin/env python3
import sys
# Constants similar to the original C++
DX = (0, 1)
DY = (1, 0)
def compute_binomials(max_i, max_j):
"""Compute binomial coefficients C[i][j] for 0 <= i <= max_i, 0 <= j <= max_j."""
C = [[0] * (max_j + 1) for _ in range(max_i + 1)]
for i in range(max_i + 1):
C[i][0] = 1
for i in range(1, max_i + 1):
for j in range(1, min(i, max_j) + 1):
C[i][j] = C[i-1][j-1] + C[i-1][j]
return C
def main():
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
numrow = int(next(it))
numcol = int(next(it))
# grid with 1-based indexing (pad with dummy at index 0)
a = [[''] * (numcol + 1) for _ in range(numrow + 1)]
for i in range(1, numrow + 1):
s = next(it)
# s length should be numcol
for j in range(1, numcol + 1):
a[i][j] = s[j-1]
need_k = int(next(it))
# Precompute binomial coefficients up to (numrow+numcol-1) choose up to max(numrow,numcol)
max_i = numrow + numcol - 1
max_j = max(numrow, numcol)
C = compute_binomials(max_i, max_j)
def ways(start_x, start_y):
"""Number of monotone paths from (start_x, start_y) to (numrow, numcol) moving only right/down."""
t1 = numrow - start_x + 1
t2 = numcol - start_y + 1
# number of moves = t1 + t2 - 2, choose where the right moves (t2-1) go
return C[t1 + t2 - 2][t2 - 1]
# pos lists for letters 'a'..'z'
pos = [[] for _ in range(26)]
def reset_pos():
for i in range(26):
pos[i].clear()
# initial current positions: start at (1,1)
cur_pos = [(1, 1)]
result_chars = []
# total length of path = numrow + numcol - 1
for _ in range(1, numrow + numcol):
# sanity checks similar to the C++ assert
assert need_k > 0 and len(cur_pos) > 0
# print the character for the first position in cur_pos
x0, y0 = cur_pos[0]
result_chars.append(a[x0][y0])
reset_pos()
# gather next-layer positions grouped by character
for (ux, uy) in cur_pos:
for t in range(2):
nxt_u = ux + DX[t]
nxt_v = uy + DY[t]
if nxt_u <= numrow and nxt_v <= numcol:
ch = a[nxt_u][nxt_v]
idx = ord(ch) - ord('a')
pos[idx].append((nxt_u, nxt_v))
# choose the letter whose accumulated paths cover the k-th path
for ii in range(26):
t = need_k
for (ux, uy) in pos[ii]:
t -= ways(ux, uy)
if t <= 0:
# choose this letter
cur_pos = pos[ii][:]
break
# skip all paths that start with this letter and continue searching
need_k = t
# The loop above appends exactly (numrow + numcol - 1) characters;
# join and output
sys.stdout.write(''.join(result_chars))
if __name__ == "__main__":
main()
