Character Equation

Time limit1sMemory limit256 MB

Summary

Given a recursive definition of a huge string T through variable concatenation equations, determine whether a pattern P is a subsequence of T without expanding T explicitly.

Level: Medium7 of 10
Topics: Dynamic programming, String, Recursion, String matching
Solved: No attempts yet

Problem

You are given a string T made of lowercase letters and a pattern P. You must decide whether P can be obtained by deleting some characters from T; that is, whether P is a subsequence of T.

For example, by deleting characters from the word programming you can obtain pong, program, or roaming. However, the order of the remaining characters must be preserved, so map cannot be formed.

T is given as a character equation that uses uppercase-letter variables. Every equation has one of the two following forms.

A = w : A is the lowercase word w.
A = B + C : A is the concatenation of the two variables B and C. (+ denotes string concatenation.)

Each variable appears on the left-hand side at most once, and following any variable's definition never leads back to itself, so there is no cycle. Therefore every variable has a uniquely determined value.

For example, consider the following equations.

START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad

Solving them gives START = goodtimesbadtimes.

Given the pattern P, the character equation, and which variable is T, write a program that decides whether P can be obtained by deleting characters from T.

Input

The first line contains the number of test cases. Each test case is structured as follows.

The first line contains the number of equations K (1 ≤ K ≤ 500). Each of the next K lines contains one equation. Every equation has one of the two forms described above and consists only of space-separated words together with + and =. Every word and variable name is at most 5 characters long. The next line gives the variable that is T. The last line contains the pattern P.

The length of P is at most 2,000.

Output

For each test case, print YES if P can be obtained by deleting characters from T, and NO otherwise.

Examples5

Example 1

Input

1
6
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
START
debate

Expected output

YES

Example 2

Input

1
6
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
START
sg

Expected output

NO

Example 3
Input
```
1
1
PROG = programming
PROG
pong
```
Expected output
```
YES
```
Example 4
Input
```
1
1
PROG = programming
PROG
map
```
Expected output
```
NO
```

Example 5

Input

1
1
PROG = programming
PROG
roaming

Expected output

YES