4132: DNA进化

每个人都知道DNA链由核苷酸组成。核苷酸有四种类型：“A”、“T”、“G”、“C”。DNA链是一个核苷酸序列。科学家们决定追踪一种稀有物种的进化，这种DNA链最初是一串的。
物种的进化被描述为DNA的一系列变化。每一个变化都是一些核苷酸的变化，例如，DNA链“AAGC”中可能发生以下变化：第二个核苷酸可以变为“T”，从而生成的DNA链是“ATGC”。
科学家们知道，DNA链的某些片段可能会受到一些未知感染的影响。它们可以作为核苷酸序列表示感染。科学家们感兴趣的是，某些感染是否会导致任何变化。因此，他们有时想知道某些感染对某些DNA片段的影响的价值。该值计算如下：
    ·感染用一字符串e表示，让科学家对从位置l到位置r的DNA链段感兴趣，包括这两个位置。
    ·字符串eee的前缀......（即由字符串e的无限多次重复组成的字符串）从位置l到位置r写在字符串s下，包括在内。
    ·撞击的价值是字符串中的字母s与其下写的字母重合的位置数。
作为一名开发人员，Innokenty对生物信息学也很感兴趣，因此科学家们向他寻求帮助。Innokenty正忙着准备VK杯，因此他决定将问题交给竞争对手。帮助科学家！

第一行包含字符串s（1 ≤ |s| ≤ 10⁵），其描述了初始DNA链。它仅由大写英文字母“A”、“T”、“G”和“C”组成。
下一行包含单个整数q（1 ≤ q ≤ 10⁵）-事件的数量。
之后，接下来的q行，每行描述一个事件。每行有两种格式之一：
    ·1 x c，其中x是整数（1 ≤ x ≤ |s|），c是字母“A”、“T”、“G”或“C”，这意味着DNA发生了变化：x位的核苷酸现在是c。
    ·2 l r e，其中l，r是整数（1 ≤ l ≤ r ≤ |s|），e是字母“A”、“T”、“G”和“C”构成的字符串（1 ≤ |e| ≤ 10） ，这意味着科学家对感染e对从位置l到位置r的DNA链片段的影响的价值感兴趣，包括在内。

对于每个科学家的查询（第二类查询），在一行中打印一个整数——感染对DNA的影响值。

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
提示

考虑第一个例子。

在第二种类型的第一个查询中，所有字符都一致，因此答案是8。

在第二个查询中，我们比较字符串“TTTTT…”和子字符串“TGCAT”。有两次撞击。

在第三个查询中，DNA更改后，我们将字符串“TATAT…”与子字符串“TGTAT”进行比较。有4次撞击。