Perfect Shuffle Verification

You are given three strings s1, s2 and result. Your task is to determine whether result is a perfect shuffle of s1 and s2. A string result is said to be a perfect shuffle of s1 and s2 if it can be formed by interleaving the characters of s1 and s2 in a way that maintains the left-to-right order of the characters from each string.

The following recurrence can be used to solve the problem using dynamic programming:

$$dp[i][j] = \begin{cases} \ true & \text{if } i = 0 \text{ and } j = 0, \ (dp[i-1][j] \quad \text{if } s1[i-1] = result[i+j-1]) \quad \lor \quad (dp[i][j-1] \quad \text{if } s2[j-1] = result[i+j-1]) & \text{otherwise.} \end{cases}$$

Print True if result is a perfect shuffle of s1 and s2, and False otherwise.

inputFormat

The input consists of three lines:

1. The first line contains the string s1.
2. The second line contains the string s2.
3. The third line contains the string result.

Note that the strings may be empty.

outputFormat

Output True if result is a perfect shuffle of s1 and s2. Otherwise, output False.

## sample

abc
def
adbcef

True