Hide

Problem D
Homework

Anthony has two multiple choice assignments to hand in today. The answer to each assignment is a string, where the $i^\textrm {th}$ letter represents the answer to the $i^\textrm {th}$ question.

But instead of handing in two strings, Anthony only hands in a single string. He claims he answered every question correctly but his little sister Cora merged his two strings into a single string. Moreover, Cora merged his string in such a way that the following conditions are satisfied:

  1. For any two integers $0\leq i<j<|s_1|$ (where $|s_1|$ is the length of $s_1$), the index of $s_1[i]$ in $s$ is less than the index of $s_1[j]$ in $s$

  2. For any two integers $0\leq i<j<|s_2|$, the index of $s_2[i]$ in $s$ is less than the index of $s_2[j]$ in $s$

Can you help Anthony’s teacher verify whether Anthony’s claim is possible?

Input

The first line contains a single string $s$. It is guaranteed that $2\leq |s|\leq 10\, 000$.

The next two lines contain strings $s_1$ and $s_2$ respectively. It is guaranteed that $1\leq |s_1|, |s_2|\leq 5\, 000$ and $|s_1|+|s_2|=|s|$.

All the strings consists of only lowercase English letters.

Output

If Anthony’s claim is possible, print “yes” (without quotes). Otherwise, print “no” (without quotes).

Sample Input 1 Sample Output 1
aabcad
aba
acd
yes
Sample Input 2 Sample Output 2
aabcad
acb
aad
no

Please log in to submit a solution to this problem

Log in