Description
Long long time ago, there's a magic kingdom call "NTHU".
Children living there need go to magic schools, "CS", when they're 13 years old.
The magic schools teach spell.
Spell have categories(詞類).
Take English for example, English have ten parts of speech, like "noun", "verb" etc.
And just like English, the spell has four parts of speech, like "Fire", "Air", "Water", and "Earth".
Besides part of speech , the spell also has its own magic grammar.
Most of the words can be classified into those four part of speech, but besides that , there are another thing in magic grammar call "spell". "Spell" means the whole sentence.
Here's a example for the grammar:
Use 1, 2, 3, 4 stands for fire, air, water, earth, and the 0 means spell, -1 means end.
Rule1: 1 1 1 -1
Rule2: 2 -1
Rule3: 3 0 4 -1
Follow the rules above , 3 2 4 -1 (water , air , earth) can be a legal spell, and so does "3 3 1 1 1 4 4 -1".
If chant it incorrectly, sometimes the spell won't work, sometimes it will blow-up.
So as a 1st grade student, the most important thing is to remember which of sententce is effective.
The homework is as following:
"Given some spell, determine whether they are effective spell or not."
Hint1 : In each grammar there is at most one "0", so it is equal to "[somthing] 0 [something]" grammar.
Hint2 : If you get RE in some testcases, you may search for "stack overflow" (堆疊溢位).
Input
First line contains two integers N, M, representing # of grammars and # of sentences.
The next N lines give the grammar. Each line contains a grammar.
The next M lines give the sentence. Each line contains a sentence.
It is guaranteed that:
- 1 ≤ N, M ≤ 100
- The length of each sentence is ≤ 100.
- There will be at most one "0" in each grammar. (For easy version)
- "0" won't appear in sentences.
Output
For each sentence output one line.
If the sentence is legal, output "True"; otherwise output "False".