외계 분자

41기는 R&E로 '외계 생명체의 유전 정보 채취해 오기'라는 매우 도전적인 주제를 골랐다. 터무니없고 실현 불가능해 보이는 주제지만, 41기는 단 한 학기 만에 외계 분자를 추출해 올 수 있었다! 이 분자는 DNA의 염기 서열처럼 일정한 유전 단위들이 일렬로 나란히 결합된 형태였다. 외계 생명체가 실존한다는 중요한 단서를 채취한 셈이다!

41기는 외계 분자를 분석하려고 분자마다 고유한 문자열을 부여했다. 외계 분자는 총 26가지 유전 단위의 조합으로 이루어져 있었다. 41기는 유전 단위를 알파벳 A부터 Z까지에 대응시켜 ABRTTWYS$\cdots$ 같은 문자열로 분자를 표현했다.

문제는 심각했다. 외계 분자는 지구의 대기와 결합하면 심각하게 변형된다. 시간이 지날수록 분자는 오염되었고, 한참 뒤에는 처음 채취했을 때와 완전히 다른 구조를 띠었다. 41기는 이 귀중한 자료를 놓치고 싶지 않았다. 그래서 다음 방법을 썼다.

41기는 외계 분자도 DNA처럼 상보적인 분자 쌍이 존재한다는 점을 관찰했다. 이를 바탕으로 외계 분자에 특정 분자 서열이 존재하는지 판단할 수 있었다. 41기는 이 방법으로 특정 시각에 외계 분자 안의 특정 분자 서열들이 존재하는지 구하고, 그 정보로 처음 형태를 대략 복원하려 했다.

당신은 신이다. 당신은 이 DNA가 앞으로 어떻게 변할지 모두 알고 있다. 이를 바탕으로 41기가 특정 시각에 특정 분자 서열들을 관찰할 수 있을지 판단해 보자!

첫 번째 줄에 문자열 $S$가 주어진다. 이는 외계 분자의 처음 모습을 나타낸다.

두 번째 줄에 41기가 확인할 문자열의 개수 $N$이 주어진다.

이후 $N$개의 줄에 걸쳐 문자열 $T_1, T_2, \cdots, T_N$이 주어진다. 참고로 $T_i$가 $S$보다 길 수도 있다.

그 다음 줄에 쿼리의 개수 $Q$가 주어진다. 그 다음 $Q$개의 줄에 걸쳐 아래의 질의가 주어진다.

• $1$ $l$ $r$ $c$: 외계 분자의 $l$번째 문자부터 $r$번째 문자까지 모두 문자 $c$로 바뀐다.
• $2$ $l$ $r$: 외계 분자의 $l$번째 문자부터 $r$번째 문자까지 고려한 문자열, 즉 부분 문자열 $S[l \cdots r]$이 $T_1, T_2, \cdots, T_N$ 중 하나와 일치하면 1, 그렇지 않으면 0을 출력한다.

2번 쿼리에 대한 답을 한 줄에 하나씩 출력한다.

2번 쿼리는 하나 이상 주어진다.

• $1\leq N\leq 1,000,000$
• $1\leq Q,|S|\leq 250,000$
• $1\leq|T_i|\leq 1,000,000$
• $1\leq\displaystyle\sum_{i=1}^{N}|T_i|\leq 1,000,000$
• $1\leq l\leq r\leq |S|$
• $S, T_i, c$는 모두 알파벳 대문자로 이루어져 있다. ($1\leq i\leq N$)

길이가 $l$인 문자열 $S$와 $1 \leq i \leq j \leq l$을 만족하는 두 정수 $i$, $j$에 대해, $S[i \cdots j]$는 $S$의 $i$번째 문자부터 $j$번째 문자까지를 순서대로 포함하는 문자열이다. 이러한 문자열을 문자열 $S$의 부분 문자열이라고 한다.

예를 들어 $S$가 ABCDABA라면, $S[1 \cdots 5]$는 ABCDA이고, $S[3 \cdots 7]$은 CDABA이다. 따라서 ABCDA와 CDABA는 문자열 ABCDABA의 부분 문자열이다. 하지만 AAAA는 문자열 ABCDABA의 부분 문자열이 아니다.

(출처: 가장 긴 공통 괄호 문자열, koi 2021)