27955번 - 외계 분자 서브태스크

문제

41기는 R&E로 '외계 생명체의 유전 정보 채취해 오기'라는 아주 도전적인 주제를 잡았다. 정말 터무니없고 실현 불가능한 주제처럼 들리겠지만, 놀랍게도 41기는 단 한 학기 만에 성공적으로 외계 분자를 추출해 올 수 있었다! 심지어 이 분자는 마치 DNA의 염기 서열과 같이 일정한 유전 단위들이 일렬로 나란히 줄지어 결합된 형태였다. 즉, 외계 생명체가 실존한다는 아주 중요한 단서를 채취한 것이다!

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

그런데 아주 심각한 문제가 생겼다. 이 외계 분자는 지구의 대기와 결합하면 심각한 변형이 일어난다. 시간이 지날수록 이 분자들은 오염되어만 갔고, 결국 한참 후에는 처음에 채취한 것과는 완전히 다른 분자 구조를 띠었다. 41기는 이 귀중한 자료를 절대로 놓치고 싶지 않았다. 그래서 다음과 같은 방법을 이용했다.

41기는 외계 분자 역시 DNA처럼 상보적인 분자 쌍이 존재한다는 특성을 관찰하였고, 이를 기반으로 외계 분자에 특정 분자 서열이 존재하는지를 판단할 수 있었다. 이를 바탕으로 41기는 해당 시각에 외계 분자에 특정 분자 서열들의 존재 여부를 구하고 이를 이용해 대략적인 처음 형태를 복원하고자 하였다.

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

입력

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

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

이후 $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ドル\cdots5$]는 ABCDA이고, $S$[3ドル\cdots7$]은 CDABA이다. 따라서 ABCDA과 CDABA은 문자열 ABCDABA의 부분 문자열이다. 하지만 AAAA은 문자열 ABCDABA의 부분 문자열이 아니다.

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