팰린드롬과 쿼리

문자열 $S$와 정수 $K$가 주어진다. 다음 두 종류의 쿼리를 처리하는 프로그램을 작성하시오.

• 1 l r c: $S[l..r]$의 모든 글자를 문자 $c$로 바꾼다.
• 2 l r: $l \le i \le j \le r$이고 $j - i + 1 \le K$인 쌍 $(i, j)$ 중에서 $S[i..j]$가 팰린드롬인 것의 개수를 출력한다.

문자열의 첫 글자의 인덱스는 $1$이다. $S[i..j]$는 $S$의 $i$번째 글자부터 $j$번째 글자까지의 부분 문자열이다.

첫째 줄에 문자열 $S$와 정수 $K$ ($1 \le K \le 50$)가 공백으로 구분되어 주어진다. $S$는 알파벳 소문자로만 이루어져 있고, 길이는 $10^5$을 넘지 않는다.

둘째 줄에 쿼리의 개수 $M$ ($1 \le M \le 10^5$)이 주어진다.

셋째 줄부터 $M$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 모든 쿼리에서 $1 \le l \le r \le |S|$이고, 1번 쿼리의 $c$는 알파벳 소문자 한 개다.

2번 쿼리마다 그 결과를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.