# L-system

Source : ACM ICPC Central European Regional 1996 |
|||

Time limit : 3 sec |
Memory limit : 32 M |

**Submitted** : 73, **Accepted** : 32

Suppose that the alphabet consists of two symbols a and b. So the set of productions includes two productions of the form a -> u, b -> v, where u and v in {a,b}+, and the starting string w in {a,b}+. Can you answer whether there exists a string in the language of the D0L system of the form xzy for a given string z? (x and y are some strings from SIGMA*, SIGMA* is the set of all strings of symbols from SIGMA, including the empty string.). Certainly you can. Write the program which will solve this problem.

**Input**

The input of the program consists of several blocks of lines. Each block includes
four lines. There are no empty lines between any successive two blocks. The
first line of a block contains the right side of the production for the symbol
a. The second one contains the right side of the production for the symbol b
and the third one contains the starting string and the fourth line the given
string z. The right sides of the productions, the given string z and the starting
string are at most 15 characters long.

**Output**

For each block in the input there is one line in the output containing
YES or NO according to the solution of the given problem.

**Sample Input**

aa bb ab aaabb a b ab ba

**Sample Output**

YES NO