시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 64 MB (%)
문제
언어학자들은 현재 목스키안이라는, 목스키 섬의 원주민들의 언어를 연구하고있다. 언어학자들은 목스키안의 원주민들이 어떻게 단어를 구성하는지 설정하는 방법과, 단어의 목록을 알아냈다. 언어학자들은 이 단어목록들 중 어떤 단어가 유효한 목스키 단어인지 알고싶어졌다. 규칙 목스키안의 단어는 아래의 규칙들을 만족해야 한다. 이 규칙들은 두가지 형태의 구성요소들을 갖는다: 변수와 단말이다. 변수는 규칙내에서 하나의 대문자로 표현된다. 단말은 모스키안 단어의 일부로 소문자로 표현한다. 여기에 두가지 종류의 규칙이 있다. 첫번째 종류의 규칙은 변수 V가 두 변수 V1 V2로 변환되는 것이며, 이것을 V->V1V2라는 짧은 형태로 표현한다. 두번째 종류의 규칙은 변수 V가 단말 t로 변환되는 것인데, V->t라는 짧은 형태로 이 규칙을 표현한다. 변수들 중 하나를 시작 변수로 잡는다. 단어 w는 영문 소문자의 조합으로 구성되어있다. 이 단어가 유효한 목스키 단어라면, 시작 변수로 부터 시작해, 이 단어 w까지 규칙들을 적용해 만들 수 있어야 한다. 예제 만약 변수 {S, A, B}와, 단말 {a,b}, 그리고 규칙이 아래와 같다고 하자. {S->AB, S->a, A->a, B->b} 단어 "ab"는 유효한 목스키 단어이며 그 이유는 다음과 같이 만들 수 있기 때문이다: S->AB->aB->ab. 단어 "a"는 S->a 형태로 간단하게 만들 수 있다. 단어 "b"는 만들 수 없다. 조건 1<=V,T<=26 1<=R1+R2<=30 1<=W<=20 언어학자들이 가진 각단어의 길이는 1에서 30 사이이다.
입력
첫번째 줄에, 두 변수 V와 T가 순서대로 주어진다. 두번째 줄에, V개의 공백으로 구분된 대문자, 변수들이 주어진다. 이 줄의 첫번째 변수는 항상 시작 변수이다. 세번째 줄에, T개의 공백으로 구분된 소문자, 단말들이 주어진다. 네번째 줄에, 정수 R1이 주어진다. 이어서 R1개의 줄에, 각 줄마다 V t의 형태로, V->t 규칙을 나타내는 정보가 주어진다. 그 다음줄에, 정수 R2가 주어진다. 이어서 R2개의 줄에, 각 줄마다 V V1 V2의 형태로 V->V1 V2 규칙을 나타내는 정보가 주어진다. 그 다음줄에, 정수 W가 주어진다. 이어서 W개의 줄에, 각 줄마다 소문자로 이루어진 단어가 하나씩 주어진다.
출력
출력은 꼭 W개의 줄로 이루어져야 한다. i번째 줄에는, i번째 단어가 유효한 목스키 단어면 1을, 아니면 0을 출력한다.
힌트
입력예제 ``` 5 2 I S A B C a b 2 A a B b 7 I A B I A C C S B S A B S A C I S S S S S 4 abababaaabbbaabbaabb abab bbaa aaabababbaaabbbb ``` 출력예제 ``` 1 1 0 1 ```