G :: Grammar

Time Limit: 10 Seconds    Memory Limit: 131072 KB

Bob is one of the best students of the Formal Languages class. Now he is learning about context free grammars in the Chomsky Normal Form (CNF). Such a grammar consists of:

 a set of nonterminal symbols N

 a set of terminal symbols T

 a special nonterminal symbol, called the start symbol S

 a set R of rules of the form A -> BC or A -> a, where A, B, C ∈ N, a ∈ T. 

If A ∈ N, we define L(A), the language generated by A, as follows:

L(A) = { wz | w ∈ L(B), ∈ L(C), where A -> BC ∈ R } ∪ { a | A -> a ∈ R }.

The language generated by the grammar with start symbol S is defined to be L(S). 

Bob must solve the following problem: for a given context free grammar in CNF, on input string x, 

determine whether x is in the language generated by the grammar, L(S).

 

Input

The program input is from a text file. It starts with the input string  x  (|x|<=1000). Follows the grammar rules, in the form ABC or Aa, each on a separate line. We consider that the start symbol is always  S.  

The input data are correct and terminate with an end of file. 

 

Output

The program prints 1 if the string is in the language generated by the grammar,  0 otherwise.The program prints the result to the standard output from the beginning of a line. 

Sample Input

a
SAB
Sa
Ab

ab
SAB
Sa
Ab

ab
SAB
Sa
Ab
Ba

Sample Output

1

0

0
Submit