给定一个由前 6 个小写英文字母（a 到 f）组成的字符串 $s[1..n]$。如果一个子串中每个不同的字母出现的次数均为偶数，则称该子串为“偶子串”。例如，在 abbacac 中有 4 个偶子串：abba、bb、acac 和 bbacac。如果同一个子串出现在不同的位置，它们将被多次计算，例如字符串 aaa 有 2 个偶子串 aa。

你需要处理 $q$ 个以下两种类型的询问：

1. 给定由两个整数 $l$ 和 $r$ 指定的范围，计算 $s[l..r]$（即从 $s[l]$ 开始到 $s[r]$ 结束的子串，两端均包含）中偶子串的数量。
2. 给定一个下标 $i$ 和一个字母 $x$（a 到 f 之间），将 $s[i]$ 修改为 $x$。

输入格式

第一行包含一个字符串 $s[1..n]$ ($1 \le n \le 2 \cdot 10^5$)，由 a 到 f 之间的字母组成。 第二行包含一个整数 $q$ ($1 \le q \le 2 \cdot 10^5$)，表示询问次数。接下来的 $q$ 行，每行给出一个询问：

• 类型 1 询问格式为 1 l r ($1 \le l \le r \le n$)。
• 类型 2 询问格式为 2 i x ($1 \le i \le n$)，其中 $x$ 是 a 到 f 之间的字母。

至少包含一个类型 1 的询问。

输出格式

对于每个类型 1 的询问，输出一行，表示偶子串的数量。

样例

样例输入 1

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

样例输出 1

4
2
6
4
0
0