짝수 부분문자열

알파벳 소문자 a부터 f까지 여섯 글자로 이루어진 문자열 $s[1..n]$이 주어진다. 부분문자열에 등장하는 서로 다른 모든 글자의 등장 횟수가 짝수이면 그 부분문자열을 짝수라고 부른다. 예를 들어 abbacac에는 짝수 부분문자열이 4개 있다: abba, bb, acac, bbacac. 같은 부분문자열이 서로 다른 위치에 나타나면 각각 따로 센다. 예를 들어 문자열 aaa에는 짝수 부분문자열 aa가 2개 있다.

다음 두 종류의 질의 q개를 처리해야 한다.

1. 두 정수 l과 r로 주어지는 구간에 대해, $s[l]$에서 시작해 $s[r]$에서 끝나는 부분문자열 $s[l..r]$에 있는 짝수 부분문자열의 개수를 센다. 양 끝을 포함한다.
2. 인덱스 i와 a부터 f까지의 글자 x가 주어지면 $s[i]$를 x로 바꾼다.

첫째 줄에 a부터 f까지의 글자로 이루어진 문자열 $s[1..n]$이 주어진다. (1 ≤ n ≤ 2 · 105)

둘째 줄에 질의의 개수 q가 주어진다. (1 ≤ q ≤ 2 · 105) 다음 q개 줄에 각각 질의가 하나씩 주어진다.

• 1번 질의는 1 l r로 주어진다. (1 ≤ l ≤ r ≤ n)
• 2번 질의는 2 i x로 주어진다. (1 ≤ i ≤ n) 여기서 x는 a부터 f까지의 글자이다.

1번 질의는 적어도 하나 있다.

각 1번 질의마다 짝수 부분문자열의 개수를 한 줄에 출력한다.