Alien Molecule

Team 41 chose a very ambitious topic for their R&E project: retrieving genetic information from alien life. It sounds absurd and impossible, but Team 41 extracted an alien molecule within a single semester! The molecule was a line of regular genetic units bonded side by side, much like the base sequence of DNA. They had captured strong evidence that alien life really exists.

To analyze the alien molecule, Team 41 gave each molecule its own string. The molecule was built from combinations of 26 kinds of genetic units. Team 41 mapped the units to the letters A to Z, so a molecule was written as a string such as ABRTTWYS$\cdots$.

Then a serious problem appeared. When the alien molecule meets Earth's atmosphere, it changes severely. Over time the molecules became contaminated, and after a long while they had a structure completely different from the one first sampled. Team 41 did not want to lose this valuable data, so they used the following method.

Team 41 observed that alien molecules, like DNA, have complementary pairs of molecules. Based on this, they could determine whether a specific molecular sequence exists in an alien molecule. Using that ability, Team 41 wanted to find which specific molecular sequences exist at a given time and use them to roughly reconstruct the original form.

You are a god. You know how this DNA will change in the future. Use that knowledge to determine whether Team 41 can observe specific molecular sequences at a given time!

The first line contains the string $S$. It describes the original form of the alien molecule.

The second line contains the number $N$ of strings that Team 41 will check.

The next $N$ lines contain the $N$ strings $T_1, T_2, \cdots, T_N$. Note that $T_i$ may be longer than $S$.

The next line contains the number of queries $Q$. The next $Q$ lines contain the following queries.

• $1$ $l$ $r$ $c$: All characters from the $l$th to the $r$th character of the alien molecule change to the character $c$.
• $2$ $l$ $r$: Consider the string formed by the $l$th to the $r$th characters of the alien molecule, that is, the substring $S[l \cdots r]$. Print 1 if it matches one of $T_1, T_2, \cdots, T_N$, and 0 otherwise.

Print the answer to each query of type 2 on its own line.

There is at least one query of type 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$ all consist of uppercase English letters. ($1\leq i\leq N$)

For a string $S$ of length $l$ and two integers $i$ and $j$ with $1 \leq i \leq j \leq l$, $S[i \cdots j]$ is the string that contains the characters of $S$ from the $i$th to the $j$th position in order. Such strings are called substrings of $S$.

For example, if $S$ is ABCDABA, then $S[1 \cdots 5]$ is ABCDA and $S[3 \cdots 7]$ is CDABA. So ABCDA and CDABA are substrings of ABCDABA. However, AAAA is not a substring of ABCDABA.

(Source: 가장 긴 공통 괄호 문자열, KOI 2021)