每个人都知道 DNA 链由核苷酸组成。核苷酸有四种类型:“A”、“T”、“G”、“C”。 DNA 链是核苷酸序列。科学家们决定追踪一种稀有物种的进化,该物种的 DNA 链最初是 string s。
物种的进化被描述为 DNA 的一系列变化。每个变化都是某个核苷酸的变化,例如,DNA链“AAGC”中可能发生以下变化:第二个核苷酸可以变为“T”,从而得到的DNA链是“ATGC”。
科学家们知道 DNA 链的某些片段可能会受到某些未知感染的影响。它们可以将感染表示为核苷酸序列。科学家们对某些感染是否会引起任何变化感兴趣。因此,他们有时想知道某些感染对 DNA 某些片段的影响价值。该值计算如下:
- 让感染表示为字符串 e,并让科学家对从位置 l 到位置 r(包括这两个位置)的 DNA 链片段感兴趣。
- 字符串 eee... 的前缀(即由字符串 e 的无限多次重复组成的字符串)写在字符串 s 下,从位置 l 到位置 r(含)。
- 影响值是字符串 s 中的字母与其下方的字母重合的位置数。
作为一名开发人员,Innokenty 对生物信息学也很感兴趣,因此科学家们向他寻求帮助。因诺肯蒂正忙于准备VK杯,因此他决定将问题委托给参赛者。帮助科学家吧!
输入
第一行包含描述初始 DNA 链的字符串 s (1 ≤ |s| ≤ 105)。它仅由大写英文字母“A”、“T”、“G”和“C”组成。
下一行包含单个整数 q (1 ≤ q ≤ 105) — 事件数。
之后是 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 的影响值。
示例
输入 #1
ATGCATGC 4 2 1 8 ATGC 2 2 6 TTT 1 4 T 2 2 6 TA
输出 #1
8 2 4
输入 #2
GAGTTGTTAA 6 2 3 4 TATGGTG 1 1 T 1 6 G 2 5 9 AGTAATA 1 10 G 2 2 6 TTGT
输出 #2
0 3 1
注意
考虑第一个例子。在第二个类型的第一个查询中,所有字符都一致,因此答案是 8。在第二个查询中,我们比较字符串“TTTTT...”和子字符串“TGCAT”。有两场比赛。在第三个查询中,DNA 更改后,我们将字符串“TATAT...”与子字符串“TGTAT”进行比较。有 4 场比赛。