알파벳과 쿼리 (Hard)

Easy 버전과 비교하면 $N$, $Q$의 제한만 다르고 나머지는 같다.

아래 두 조건을 만족하는 부분 문자열을 알파벳 묶음이라고 하자.

• 하나의 동일한 알파벳으로만 문자열이 이루어져 있어야 한다.
• 전체 문자열에서 해당 부분 문자열을 포함하는 더 긴 부분 문자열로 알파벳 묶음을 만들 수 있으면 그 부분 문자열은 알파벳 묶음이 아니다.

예를 들어 AAABBAAC라는 문자열에서 알파벳 묶음은 AAA, BB, AA, C로 4개다. 같은 문자열에서 B, AC는 조건을 만족하지 않으므로 알파벳 묶음이 아니다.

영어 대문자로만 이루어진 길이 $N$의 문자열 $S = S_1 S_2 \dots S_N$이 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하라.

• 1 l r: 부분 문자열 $S_l S_{l+1} \dots S_r$에서 알파벳 묶음의 개수를 출력한다.
• 2 l r: 부분 문자열 $S_l S_{l+1} \dots S_r$의 모든 알파벳을 알파벳 순서상 다음 알파벳으로 바꾼다. 단, Z는 A로 바꾼다.

부분 문자열 $S_l S_{l+1} \dots S_r$은 $S$의 $l$번째 문자부터 $r$번째 문자까지를 순서대로 포함하는 부분 문자열이다.

첫 번째 줄에 문자열의 길이 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. $(3 \leq N, Q \leq 200 \ 000)$

두 번째 줄에 영어 대문자로만 이루어진 길이 $N$의 문자열 $S$가 주어진다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. $(1 \leq l \leq r \leq N)$

1번 쿼리는 한 번 이상 주어진다.

1번 쿼리의 결괏값을 입력으로 주어진 순서대로 한 줄에 하나씩 출력한다.