Chomsky Normal Form Grammar

Time limit5sMemory limit256 MB

Summary

Decide whether a given string of up to 1000 lowercase letters belongs to the language generated from start symbol S by a CNF grammar.

Level: Medium5 of 10
Topics: Dynamic programming, Intervals
Solved: No attempts yet

Problem

A context free grammar is given in Chomsky Normal Form (CNF). Such a grammar consists of the following.

a set $N$ of nonterminal symbols
a set $T$ of terminal symbols
a start symbol $S$ that belongs to $N$
a set $R$ of rules of the form $A \to BC$ or $A \to a$ , where $A, B, C \in N$ and $a \in T$

For $A \in N$ , the language $L(A)$ generated by $A$ is defined as follows.

$L(A) = \{\,wz \mid w \in L(B),\ z \in L(C),\ A \to BC \in R\,\} \cup \{\,a \mid A \to a \in R\,\}$

The language generated by the grammar is the language of the start symbol, $L(S)$ . Given a string $x$ , decide whether $x$ belongs to $L(S)$ .

Input

The first line contains the string $x$ . It consists of lowercase letters only and its length is between 1 and 1000.

From the second line to the end of the file, each line holds one grammar rule. Nonterminal symbols are written as uppercase letters and terminal symbols as lowercase letters. A line ABC of length 3 means the rule $A \to BC$ , and a line Aa of length 2 means the rule $A \to a$ . The start symbol is always S. At least one rule is given, and the same rule can appear more than once.

Output

Print 1 on one line if $x$ belongs to the language generated by the grammar, and 0 otherwise.

Examples4

Example 1
Input
```
a
SAB
Sa
Ab
```
Expected output
```
1
```
Example 2
Input
```
ab
SAB
Sa
Ab
```
Expected output
```
0
```
Example 3
Input
```
ab
SAB
Sa
Ab
Ba
```
Expected output
```
0
```
Example 4
Input
```
ba
SAB
Sa
Ab
Ba
```
Expected output
```
1
```