String Table

Time limit2sMemory limit512 MB

Summary

Build a table whose cells are huge concatenated strings defined by comparing neighbors, then print 50 characters from a given position of the final cell.

Level: Hard8 of 10
Topics: Dynamic programming, String, Recursion, Divide and conquer
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples5

Example 1
Input
```
ad
cb
0
```
Expected output
```
acbacd
```
Example 2
Input
```
fox
cat
0
```
Expected output
```
acfcfoacftacfcfocfox
```

Example 3

Input

Ra6b1t
W0lf
66

Expected output

RWab0RWRWa0RWl0RWRWa6RWa0RWRWa6RWa6RWab0RWRWa6RWa6

Example 4
Input
```
M0HAXG
COFU12
919
```
Expected output
```
MOFU2
```

Example 5

Input

a0B1c2D3e4F5gHiJkLmN
A9b8C7d6EfGhIjKlMn
9876543210

Expected output

B10AaB1c0Aa9Aa0AaB0AaB10AaB1c0AaB1c20Aa9Aa0AaB0Aa9