Mhocskian 언어

언어학자들이 Mhocsky 섬 원주민의 언어인 Mhocskian을 연구하고 있다. 이들은 원주민이 단어를 만드는 방법에 대한 설명과 단어 목록을 발견했고, 그 목록의 단어들 중 어떤 것이 올바른 Mhocskian 단어인지 알고 싶어 한다.

Mhocskian의 단어는 두 종류의 기호로 만들어진다.

• 변수(variable)는 단어를 만드는 과정에서만 사용되는 대문자이다.
• 종단 기호(terminal)는 완성된 단어에 실제로 나타나는 소문자이다.

규칙에는 두 종류가 있다.

• $V \rightarrow V_1 V_2$ 는 변수 $V$ 를 두 변수 $V_1 V_2$ 로 (그 순서대로) 바꾼다.
• $V \rightarrow t$ 는 변수 $V$ 를 종단 기호 $t$ 로 바꾼다.

변수 중 하나는 시작 변수이다. 소문자로 이루어진 단어 $w$ 는, 시작 변수에서 출발하여 규칙들을 차례로 적용해 정확히 $w$ 를 만들어 낼 수 있으면 올바른 Mhocskian 단어이다. 예를 들어 시작 변수가 $S$ 이고 규칙이 $S \rightarrow AB$, $A \rightarrow a$, $B \rightarrow b$ 라면, $S \rightarrow AB$ 를 적용한 뒤 $A \rightarrow a$ 와 $B \rightarrow b$ 를 적용하여 단어 $ab$ 를 만들 수 있으므로 $ab$ 는 올바른 단어이다.

규칙과 단어 목록이 주어질 때, 각 단어가 올바른 Mhocskian 단어인지 판별하여라.

• 첫째 줄에 두 정수 $V$ 와 $T$ 가 주어진다. 각각 변수의 개수와 종단 기호의 개수이다.
• 둘째 줄에 공백으로 구분된 $V$ 개의 대문자, 즉 변수들이 주어진다. 그중 첫 번째가 시작 변수이다.
• 셋째 줄에 공백으로 구분된 $T$ 개의 소문자, 즉 종단 기호들이 주어진다.
• 넷째 줄에 정수 $R_1$ 이 주어진다. 이어지는 $R_1$ 개의 줄은 각각 V t 형태이며 규칙 $V \rightarrow t$ 를 나타낸다.
• 다음 줄에 정수 $R_2$ 가 주어진다. 이어지는 $R_2$ 개의 줄은 각각 V V1 V2 형태이며 규칙 $V \rightarrow V_1 V_2$ 를 나타낸다.
• 다음 줄에 정수 $W$ 가 주어진다. 이어지는 $W$ 개의 줄에는 각각 소문자로만 이루어진 단어가 하나씩 주어진다.

$W$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 단어가 올바른 Mhocskian 단어이면 1 을, 그렇지 않으면 0 을 출력한다.

• $1 \le V, T \le 26$
• $1 \le R_1 + R_2 \le 30$
• $1 \le W \le 20$
• 목록의 각 단어의 길이는 $1$ 이상 $30$ 이하이다.