题目描述
给定一个只含小写字母的字符串 $S$，有 $Q$ 次操作，操作有以下两种：
1 i c：将 $S_i$ 修改为 $c$（$1\le i\le |S|$，$c$ 是小写字母）。2 l r：查询 $S[l...r]$ 有多少回文后缀（$1\le l\le r\le |S|$）。
输入格式
第一行一个只含小写字母的字符串 $S$（$|S|\le 2\times 10^5$）。
第二行一个整数 $Q$（$Q\le 2\times 10^5$），表示操作次数。
接下来 $Q$ 行，每行是一个操作。
本题强制在线，如果是操作 $1$，那么要将输入的 $i$ 异或上 $lastans$，如果是操作 $2$，那么要将 $l$ 和 $r$ 都异或上 $lastans$。$lastans$ 是上一次操作 $2$ 的答案，如果没有上一次操作 $2$，则 $lastans=0$。
输出格式
对每个操作 $2$ 输出一行答案。
样例
Input1
abbbaabbba
7
2 10 10
1 9 a
1 11 b
2 6 9
1 9 a
1 6 a
2 2 6Output1
1
1
3解密后的输入为：
abbbaabbba
7
2 10 10
1 8 a
1 10 b
2 7 8
1 8 a
1 7 a
2 3 7对于第 $1$ 个操作，查询字符串为：a，回文后缀有 a。
对于第 $4$ 个操作，查询字符串为：ba，回文后缀有 a。
对于第 $7$ 个操作，查询字符串为：bbaaa，回文后缀有 a、aa 和 aaa。
Input2
abaabaabbaabbaabaaba
10
2 15 19
2 8 18
2 6 15
2 14 13
2 8 15
2 1 16
2 14 21
2 9 12
2 4 17
2 5 12Output2
2
2
3
1
2
4
2
2
3
4解密后的输入为：
abaabaabbaabbaabaaba
10
2 15 19
2 10 16
2 4 13
2 13 14
2 9 14
2 3 18
2 10 17
2 11 14
2 6 19
2 6 15数据范围
对所有数据满足：$1\le |S|,Q\le 2\times 10^5$。
详细子任务附加限制及分值如下表所示：
| 子任务编号 | $\lvert S\rvert \le$ | $\lvert Q\rvert \le $ | 特殊性质 | 分值 | 子任务依赖 |
|---|---|---|---|---|---|
| $1$ | $5 \times 10^3$ | $ 5 \times 10^3$ | / | $10$ | / |
| $2$ | $2 \times 10^5$ | $2 \times 10^5$ | 没有操作 $1$ | $10$ | |
| $3$ | $S_i$ 和 $c$ 在 $\{\mathtt{a}, \mathtt{b}\}$ 中均匀独立随机，操作 $1$ 中 $i$ 在 $[1, \lvert S \rvert]$ 中均匀独立随机 | $10$ | |||
| $4$ | 操作 $2$ 中 $l=1, r=\lvert S \rvert$ | $10$ | |||
| $5$ | / | $30$ | $1$ | ||
| $6$ | $30$ | $1 \sim 5$ |