문자열 변환과 쿼리 2

알파벳 대소문자로 이루어진 문자열 $S$가 주어진다. 또한 $S$에 대한 $n$개의 질의가 저장된 질의 목록 $A$가 주어진다. 질의는 다음 두 가지 유형 중 하나이다.

• 유형 1은 1 i1 i2 형태이며, $S$에 있는 모든 문자 $i_1$을 문자 $i_2$로 바꾼다. $S$에 문자 $i_1$이 없으면 $S$는 바뀌지 않는다.
• 유형 2는 2 형태이다. 지금까지 주어진 유형 1의 질의를 순서대로 $S$에 적용한 결과를 문자열 $T$라고 하자. $T$에서 같은 문자로만 이루어진 부분 문자열의 최대 길이를 출력한다. 부분 문자열은 $T$에서 연속된 일부이다.

질의 목록 $A$를 첫 번째 질의부터 순서대로 처리하면서 유형 2 질의의 결과를 출력한다.

첫 번째 줄에 문자열 $S$와 정수 $n$이 공백으로 구분되어 주어진다.

이어서 $n$개의 줄에 질의가 첫 번째 질의부터 순서대로 한 줄에 하나씩 주어진다. 유형 1은 정수 1, 문자 $i_1$, $i_2$가 공백으로 구분되어 주어지고, 유형 2는 정수 2만 주어진다.

유형 2 질의의 결과를 순서대로 한 줄에 하나씩 출력한다.

• $1 \le |S| \le 300000$이며, $S$는 알파벳 대소문자로 이루어진다.
• $1 \le n \le 300000$.
• 질의 목록 $A$에는 유형 1과 유형 2의 질의만 있다.
• $A$에는 유형 2 질의가 1개 이상 있다.
• $|S| \times$ (유형 2 질의의 수) $\le 10^8$.
• $i_1$, $i_2$는 알파벳 대소문자이다.