eolymp
bolt
Try our new interface for solving problems
Problems

Word equations

Word equations

Time limit 1 second
Memory limit 128 MiB

You are given a text T and a pattern P. You want to check if you can erase some of the letters of T so that the remaining symbols produce exactly P. For example, the word programming can be partially erased to obtain pong or program orroaming (but not map, as the letters must remain in the same order). Both words consist of small letters of the English alphabet only.

There is just one catch: the text T is encoded by a system of equations. The equations use special symbols (every symbol is denoted by a word in capital letters), each of them encoding some word over the alphabet {a,...,z}. Each equation is of one of the following forms:

A = a word over {a,...,z}

or

A = B + C

where A, B, C can be any special symbols, and the + sign denotes the concatenation of words. The system is:

  • unambiguous - for a fixed symbol A, there is exactly one equation with A on the left-hand side, and

  • a cyclic - if you start from any symbol A and make substitutions according to the equations (right-hand side for left-hand side), you can never obtain an expression containing A again.

Such a system always has a unique solution. For example, in the system:

  • START = FIRST + SECND

  • FIRST = D + E

  • SECND = F + E

  • D = good

  • E = times

  • F = bad

the symbol START encodes the word goodtimesbadtimes.

Given a single word P as the pattern, a system of equations, and one particular starting symbol S of this system, determine whether the pattern P is present in the word encoded by S.

Input data

The first line contains the number of test cases t. The descriptions of the test cases follow:

Each test case starts with a line containing a single integer k (1k500) - the number of equations. The next k lines contain equations. Each of them has one of the two forms given in the problem statement, with spaces separating words, plus signs, and equation signs. Each word (including symbol names) is at least one and at most five characters long.

The next line contains a single special symbol (a word in capital letters), while the final line contains a non-empty word of at most 2000 lowercase letters. These are the starting symbol and the pattern to find, respectively.

Output data

For each test case print the answer in a separate line: YES if the pattern appears in the given encoded word, and NO otherwise.

Examples

Input example #1
1
6
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
START
debate
Output example #1
YES
Source 2012 ACM Central Europe Regional Contest, Kraków, November 16-18, Problem E