L-시스템 부분 문자열

D0L 시스템(상호작용이 없는 결정론적 린덴마이어 시스템)은 유한한 알파벳 $\Sigma$, 유한한 생성 규칙 집합 $P$, 그리고 시작 문자열 $w$로 이루어진다. 각 생성 규칙은 $x \to u$ 꼴이며, 여기서 $x \in \Sigma$이고 $u \in \Sigma^{+}$($\Sigma$의 기호로 이루어진 비어 있지 않은 문자열)이다. 모든 기호 $x \in \Sigma$에 대해 왼쪽이 $x$인 규칙이 $P$ 안에 정확히 하나 존재한다.

직접 유도는 문자열의 모든 기호를 각 기호에 대응하는 규칙의 오른쪽 문자열로 동시에 치환하여 새 문자열을 만드는 것이다. 이 시스템의 언어는 시작 문자열 $w$에서 직접 유도를 0번 이상 적용하여 얻을 수 있는 모든 문자열의 집합이다(따라서 $w$ 자신도 언어에 속한다).

이 문제에서 알파벳은 $\Sigma = \{a, b\}$이므로 규칙은 정확히 두 개, $a \to u$와 $b \to v$이며 $u, v \in \{a, b\}^{+}$이고 시작 문자열은 $w \in \{a, b\}^{+}$이다.

문자열 $z$가 주어질 때, 언어 안에 $x\,z\,y$ ($x, y \in \{a, b\}^{*}$) 꼴의 문자열이 하나라도 존재하는지, 즉 $z$가 언어에 속한 어떤 문자열의 (연속된) 부분 문자열로 나타나는지 판정하여라.

입력은 여러 개의 블록으로 이루어지며 파일의 끝에서 종료된다. 연속한 두 블록 사이에 빈 줄은 없다. 각 블록은 정확히 네 줄로 이루어진다.

1. 규칙 $a \to u$의 오른쪽 문자열 $u$
2. 규칙 $b \to v$의 오른쪽 문자열 $v$
3. 시작 문자열 $w$
4. 질의 문자열 $z$

이 네 문자열은 모두 비어 있지 않고, 문자 $a$와 $b$만으로 이루어지며, 길이는 최대 $15$이다.

각 블록마다 한 줄에, 언어에 속한 어떤 문자열이 $z$를 부분 문자열로 포함하면 YES를, 그렇지 않으면 NO를 출력한다.