K. Subwords
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have a grammar with the start symbol $$$S$$$, a set of variables $$$V$$$, a set of terminal symbols $$$T$$$, and a set of rules $$$P$$$. Every upper-case letter is a variable, so $$$V=\{A,\dots,Z\}$$$, and every lower-case letter is a terminal symbol, so $$$T=\{a,\dots,z\}$$$. A rule is of the form $$$A\to \alpha$$$, where $$$A\in V$$$ is a variable and $$$\alpha$$$ is a string consisting of variables and terminal symbols. The grammar never contains chain rules of the form $$$A\to B$$$, where the right side consists of a single variable. Rules of the form $$$A\to b$$$ are possible, where the right side consists of a single terminal.

A word can be derived by starting with $$$\alpha=S$$$ and then repeatedly choosing some variable $$$X$$$ in $$$\alpha$$$, some rule $$$X\to\beta$$$, and then replacing one $$$X$$$ in $$$\alpha$$$ with $$$\beta$$$. To be precise, if $$$\alpha=\alpha'X\alpha"$$$ and we have a rule $$$X\to\beta$$$, then we can replace $$$\alpha$$$ with $$$\alpha'\beta\alpha"$$$, and we write $$$\alpha\Rightarrow \alpha'\beta\alpha"$$$.

Here is a complete example. The grammar has the rules $$$$$$ S\to SA,\ \ \ S\to b,\ \ \ A\to bS,\ \ \ A\to a. $$$$$$ Then we can derive the word $$$bbb$$$ in four steps: $$$$$$ S\Rightarrow SA\Rightarrow bA\Rightarrow bbS\Rightarrow bbb. $$$$$$

On the other hand, the word $$$aaa$$$ cannot be derived.

Your task is to answer the following question for a grammar $$$G$$$ and a word $$$w$$$ (consisting of terminal symbols):

  • Can you add zero or more terminal symbols at the beginning of $$$w$$$ and zero or more terminal symbols at the end of $$$w$$$ such that the resulting word $$$uwv$$$ can be derived by $$$G$$$?
Input

The first line contains an integer $$$k$$$, representing the number of rules.

Followed by $$$k$$$ lines, each of which contains one rule. A rule is encoded by its left side, followed by ->, and then followed by its right side.

The last line contains the word $$$w$$$, representing the input word of the question.

  • $$$1\leq k\leq 25$$$
  • The left side of every rule is an upper-case letter.
  • The right side of every rule is a string of upper-case and lower-case letters. Moreover, it is either a string of length at least $$$2$$$ or a single lower-case letter.
  • The total length of the right sides of all rules is at most $$$100$$$.
  • The length of $$$w$$$ is at least $$$1$$$ and at most $$$400$$$, and $$$w$$$ consists of lower-case letters.
Output

Output a single line containing Yes or No that answers the question.

Examples
Input
4
S -> SA
S -> b
A -> bS
A -> a
bbb
Output
Yes
Input
2
S -> aSb
S -> ab
ba
Output
No
Input
2
S -> aSa
S -> b
ab
Output
Yes