String Table

You are given two strings $s$ and $t$. All characters in the two strings are distinct: no character appears twice, no character of $s$ appears in $t$, and no character of $t$ appears in $s$.

Let $N$ be the length of $s$ and $M$ the length of $t$. A two-dimensional array table is defined as follows.

• table[i][0] = s[i-1] ($1 \le i \le N$)
• table[0][j] = t[j-1] ($1 \le j \le M$)
• table[i][j] = min(table[i-1][j], table[i][j-1]) + max(table[i-1][j], table[i][j-1]) ($1 \le i \le N$, $1 \le j \le M$)

min returns whichever of the two strings comes first in lexicographic order, and max returns the one that comes later. Characters are compared by ASCII code, so digits come before uppercase letters and uppercase letters come before lowercase letters. A+B is the string A followed by the string B.

Write a program that finds a substring of table[N][M]. Because the string can be very long, print only the $\min(50, L - pos)$ characters starting at position $pos$. Here $L$ is the length of table[N][M], and positions are counted from 0.

The first line contains $s$, the second line contains $t$, and the third line contains $pos$ ($0 \le pos < L$).

The lengths of $s$ and $t$ are each between 1 and 30, inclusive. Both strings consist only of uppercase letters, lowercase letters, and digits.

Print, on the first line, the substring of table[N][M] that consists of the $\min(50, L - pos)$ characters starting at position $pos$.