String Conversion and Queries 2

A string $S$ consisting of uppercase and lowercase English letters is given. A list $A$ of $n$ queries on $S$ is also given. Each query is one of two types.

• Type 1, written as 1 i1 i2: Replace every character $i_1$ in $S$ with the character $i_2$. If $S$ has no character $i_1$, $S$ does not change.
• Type 2, written as 2: Apply all type 1 queries given so far to $S$, in order. Let $T$ be the resulting string. Output the maximum length of a substring of $T$ made of one repeated character. A substring is a contiguous part of $T$.

Process the queries in $A$ from first to last and output the result of each type 2 query.

The first line contains the string $S$ and the integer $n$, separated by a space.

Each of the next $n$ lines contains one query, in order from the first to the last. A type 1 query is given as the integer 1 followed by the characters $i_1$ and $i_2$, separated by spaces. A type 2 query is given as the integer 2 alone.

For each type 2 query, print its result on its own line, in order.

• $1 \le |S| \le 300000$, where $S$ consists of uppercase and lowercase English letters.
• $1 \le n \le 300000$.
• $A$ contains only type 1 and type 2 queries.
• $A$ contains at least one type 2 query.
• $|S| \times$ (the number of type 2 queries) $\le 10^8$.
• $i_1$ and $i_2$ are uppercase or lowercase English letters.