시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 4 3 3 75.000%

문제

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), z ∈ 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).

입력

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. The program prints the result to the standard output from the beginning of a line. 

출력

The program prints 1 if the string is in the language generated by the grammar, 0 otherwise.

예제 입력

a
SAB
Sa
Ab

예제 출력

1

예제 입력 2

ab
SAB
Sa
Ab

예제 출력 2

0

예제 입력 3

ab
SAB
Sa
Ab
Ba

예제 출력 3

0

힌트

Input/output samples are given in the table below. There are three tests. The first two use the same grammar: SAB, Sa, Ab (S→AB, S→a, A→b). For the first test the input string is a, and the result is 1, while for the second test the input string is ab and the result is 0.