Problem F
Even Substrings

Image from theconversation.com

You are given a string $s[1..n]$ consisting of the first $6$ lowercase English letters between a and f. A substring is called even if every distinct letter in it appears an even number of times. For example, in abbacac there are $4$ even substrings: abba, bb, acac, bbacac. If a same substring appears at different locations, they shall be counted multiple times, e.g. the string aaa has $2$ even substrings aa.

You are to process $q$ queries of the following two types:

1. Given a range specified by two integers $l$ and $r$, count the number of even substrings in $s[l..r]$, the substring of $s$ starting at $s[l]$ and ending at $s[r]$ (both ends are inclusive).

2. Given an index $i$ and a letter $x$ between a and f, change $s[i]$ to $x$.

Input

The first line of input has a single string $s[1..n]$ ($1 \leq n \leq 2 \cdot 10^5$) consisting of letters between a and f.

The second line of input has a single integer $q$ ($1 \leq q \leq 2 \cdot 10^5$), the number of queries. Each of the next $q$ lines gives one query:

• Type $1$ query has $1~ l~ r$ ($1 \leq l \leq r \leq n$).

• Type $2$ query has $2~ i~ x$ ($1 \leq i \leq n$), where $x$ is a letter between a and f.

There is at least one query of type $1$.

Output

For each type $1$ query output the number of even substrings on a single line.

abbacac
8
1 1 7
2 5 a
1 4 6
1 1 7
2 6 b
1 2 6
1 5 7
1 1 1

4
2
6
4
0
0