Rhyming Slang

Time limit2sMemory limit512 MB

Summary

Given a word and lists of rhyming endings, decide for each phrase whether its last word shares a rhyming ending with the word.

Level: Easy3 of 10
Topics: String, Hash map, Implementation
Solved: No attempts yet

Problem

Rhyming slang replaces a common word with a phrase of two or three words whose last word rhymes with the original word. For example:

replace stairs with apples and pears,
replace rotten with bales of cotton.

English spelling and pronunciation vary so much that a non-native speaker cannot always tell which words rhyme.

You are given several lists, each holding word endings that sound the same. Two words rhyme when one list holds an ending that is a suffix of the first word and an ending that is a suffix of the second word. The two endings do not have to be equal, but they must come from the same list.

Given a common word, the lists of endings, and several phrases, decide for each phrase whether it could be rhyming slang for that word.

Input

The first line contains the common word $S$ ( $1 \le |S| \le 20$ ).
The second line contains $E$ ( $1 \le E \le 10$ ), the number of lists of endings that sound the same.
Each of the next $E$ lines contains one list, at most 100 characters long, holding endings separated by spaces.
The next line contains $P$ ( $1 \le P \le 10$ ), the number of phrases to test.
Each of the next $P$ lines contains one phrase $p_i$ , at most 100 characters long, made of one to three words separated by single spaces.

All letters are lower case. The ending of $S$ appears on at least one list.

Output

Print $P$ lines. On line $i$ print YES if the last word of phrase $p_i$ rhymes with $S$ , and NO otherwise.

Examples3

Example 1

Input

stairs
2
erres airs ears ares aires
eet eat
2
apples and pears
plates of meat

Expected output

YES
NO

Example 2

Input

drought
2
aught ought aut acht
ought oubt outte out oute
5
tasty sprout
difficult route
worried and fraught
forever in doubt
apples and pears

Expected output

YES
YES
YES
YES
NO

Example 3

Input

listen
1
issen isten ison
2
glisten
listen

Expected output

YES
YES