교배

Just Odd Investigations Laboratory를 아는가? 이 연구소의 업무는 "just odd investigations"를 하는 것이다. 이하에서는 이 연구소를 줄여서 JOI 연구소라고 부른다.

최근 세계 여러 역사 유적에서 화려한 꽃이 피는 넓은 정원이 발견되었다. JOI 연구소는 이 정원의 꽃이 신종이며 그 유전자가 비슷한 특징을 가진다는 것을 알아냈다. 이 신종 꽃의 유전자는 J, O, I로 이루어진 길이 N의 문자열이다. 이 문자열을 유전자 서열이라고 부른다.

당신은 JOI 연구소에서 일하는 연구원이다. 당신은 처음에 신종 꽃 세 송이를 가지고 있다. 그 유전자 서열은 각각 SA, SB, SC이다.

신종 꽃 두 송이로부터 교배라는 연산을 통해 새로운 신종 꽃 한 송이를 얻을 수 있다. 새 꽃의 유전자 서열의 i번째 문자 (1 ≤ i ≤ N)는 다음 규칙으로 결정된다.

• 두 꽃의 유전자 서열의 i번째 문자가 같으면, 새 꽃의 유전자 서열의 i번째 문자는 그 문자와 같다.
• 두 꽃의 유전자 서열의 i번째 문자가 다르면, 새 꽃의 유전자 서열의 i번째 문자는 J, O, I 중 이 두 문자와 다른 문자이다.

다시 말해, 두 꽃의 유전자 서열의 i번째 문자가 c1, c2라면 새 꽃의 유전자 서열의 i번째 문자 c3는 다음 표와 같다.

같은 꽃을 교배에 몇 번이든 사용할 수 있다. 교배로 새 꽃을 얻으면 그 꽃을 이후 교배에 사용할 수 있다.

더 아름다운 꽃을 얻기 위해 JOI 연구소는 0부터 Q까지 번호가 붙은 (Q + 1)개의 유전자 서열을 후보 유전자 서열로 제안했다. 후보 유전자 서열을 설명하는 목록이 주어진다. 이 목록에는 문자열 T0과, 각 j (1 ≤ j ≤ Q)에 대해 정수 Lj, Rj와 문자 Cj가 들어 있다. 후보 유전자 서열은 다음과 같이 주어진다.

• 후보 유전자 서열 0은 T0이다.
• 후보 유전자 서열 j (1 ≤ j ≤ Q)는 후보 유전자 서열 j − 1의 Lj번째 위치부터 Rj번째 위치까지의 문자를 문자 Cj로 바꾼 것이다.

정수 N, 처음 세 송이 꽃의 유전자 서열, 후보 유전자 서열을 설명하는 목록이 주어질 때, 각 후보 유전자 서열마다 처음 세 송이의 꽃으로부터 교배를 0번 이상 해서 주어진 유전자 서열을 가진 꽃을 얻을 수 있는지 판정하는 프로그램을 작성하라.

다음 데이터를 표준 입력에서 읽는다.

N
SA
SB
SC
Q
T0
L1 R1 C1
.
.
.
LQ RQ CQ

표준 출력에 (Q + 1)개의 줄을 출력한다. (j + 1)번째 줄 (0 ≤ j ≤ Q)에는 처음 세 송이의 꽃으로부터 교배를 0번 이상 해서 후보 유전자 서열 j를 가진 꽃을 얻을 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

• 1 ≤ N ≤ 200 000.
• SA, SB, SC는 길이 N의 문자열이다. 각 문자는 J, O, I 중 하나이다.
• 1 ≤ Q ≤ 200 000.
• T0는 길이 N의 문자열이다. 각 문자는 J, O, I 중 하나이다.
• 1 ≤ Lj ≤ Rj ≤ N (1 ≤ j ≤ Q).
• Cj는 J, O, I 중 하나이다 (1 ≤ j ≤ Q).