题目描述

DNA 链由核苷酸组成。有四种类型的核苷酸：A，T，G，C。DNA 链是核苷酸序列。科学家决定追踪一种稀有物种的进化，它最初的 DNA 链为 $s$。

物种的进化被描述为 DNA 的一系列变化。每个变化都是某些核苷酸的变化，例如，DNA 链 AAGC 中可能发生以下变化：第二个核苷酸可以变为 T，然后变成 ATGC。

科学家们知道 DNA 链的某些片段会受到某些未知感染的影响。这些感染可以被表示为核苷酸序列。科学家们对引起变化的感染十分感兴趣。因此，他们有时想知道某些感染对某些 DNA 片段的影响的价值。价值是这样计算的：

• 用字符串 $e$ 表示感染的核苷酸序列，科学家们对 DNA 序列从 $l$ 到 $r$（包括端点）的片段感兴趣。
• 把字符串 $eee..$的前缀（即字符串 $e$ 重复许多次组成的字符串）写在字符串 $s$ 从 $l$ 到 $r$（包括端点）的片段下边。
• 感染对 DNA 片段的价值是感染与 DNA 片段在 $l$ 到 $r$ 区间内，相同位置相同的核苷酸的数量。

作为开发者，Innokenty 也对生物信息学感兴趣，因此科学家们向他求助。Innokenty 正在忙着准备 VK 杯，所以他决定将问题交给参赛者们。来帮帮科学家们吧！

输入格式

第一行一个字符串 $s$，$1 \le |s| \le 10^5$，仅由字母 A，T，G，C 组成。

接下来一个整数 $q$，$1 \le q \le 10^5$。

接下来 $q$ 行，每行格式如下：

• 1 x c，表示将第 $x$ 个字母变为 $c$。
• 2 l r e，表示询问字符串 $e$ 对 DNA 序列从 $l$ 到 $r$（包括端点）的片段的影响的价值。

输出格式

对于每个询问，在一行中输出一个整数表示答案。

ATGCATGC
4
2 1 8 ATGC
2 2 6 TTT
1 4 T
2 2 6 TA

8
2
4

GAGTTGTTAA
6
2 3 4 TATGGTG
1 1 T
1 6 G
2 5 9 AGTAATA
1 10 G
2 2 6 TTGT

0
3
1