CF827C.DNA Evolution

Everyone knows that DNA strands consist of nucleotides. There are four types of nucleotides: "A", "T", "G", "C". A DNA strand is a sequence of nucleotides. Scientists decided to track evolution of a rare species, which DNA strand was string s initially.

Evolution of the species is described as a sequence of changes in the DNA. Every change is a change of some nucleotide, for example, the following change can happen in DNA strand "AAGC": the second nucleotide can change to "T" so that the resulting DNA strand is "ATGC".

Scientists know that some segments of the DNA strand can be affected by some unknown infections. They can represent an infection as a sequence of nucleotides. Scientists are interested if there are any changes caused by some infections. Thus they sometimes want to know the value of impact of some infection to some segment of the DNA. This value is computed as follows:

• Let the infection be represented as a string e, and let scientists be interested in DNA strand segment starting from position l to position r, inclusive.
• Prefix of the string eee... (i.e. the string that consists of infinitely many repeats of string e) is written under the string s from position l to position r, inclusive.
• The value of impact is the number of positions where letter of string s coincided with the letter written under it.

Being a developer, Innokenty is interested in bioinformatics also, so the scientists asked him for help. Innokenty is busy preparing VK Cup, so he decided to delegate the problem to the competitors. Help the scientists!

众所周知，DNA链由核苷酸组成。核苷酸共有四种类型：“A”、“T”、“G”、“C”。DNA链即为一个核苷酸序列。科学家们决定追踪某稀有物种的进化过程，该物种最初的DNA链为字符串 $s$。

该物种的进化过程被描述为DNA链的一系列变化。每次变化均涉及某个核苷酸的替换；例如，在DNA链 “AAGC” 中，第二个核苷酸可变为 “T”，从而得到新的DNA链 “ATGC”。

科学家们发现，DNA链的某些区段可能受到某些未知感染的影响。他们可将一次感染表示为一个核苷酸序列。科学家们希望了解是否存在由某些感染引发的变化。因此，他们有时需要计算某次感染对DNA链某一段的影响值（impact value）。该值按如下方式计算：

• 设感染表示为字符串 $e$，科学家关注的DNA链区段为从位置 $l$ 到位置 $r$（含端点）。
• 将字符串 $eee\ldots$（即字符串 $e$ 无限重复构成的字符串）的一个前缀，自位置 $l$ 起至位置 $r$ 止（含端点），逐位写在字符串 $s$ 的对应区段下方。
• 影响值即为字符串 $s$ 中与下方所写字母相同的字符位置个数。

作为一名开发者，Innokenty 对生物信息学也很感兴趣，因此科学家们向他寻求帮助。但Innokenty正忙于筹备VK Cup，于是他决定将该问题委托给各位参赛者。请帮助科学家们！

The first line contains the string s (1 ≤ |s| ≤ 105) that describes the initial DNA strand. It consists only of capital English letters "A", "T", "G" and "C".

The next line contains single integer q (1 ≤ q ≤ 105) — the number of events.

After that, q lines follow, each describes one event. Each of the lines has one of two formats:

• 1 x c, where x is an integer (1 ≤ x ≤ |s|), and c is a letter "A", "T", "G" or "C", which means that there is a change in the DNA: the nucleotide at position x is now c.
• 2 l r e, where l, r are integers (1 ≤ l ≤ r ≤ |s|), and e is a string of letters "A", "T", "G" and "C" (1 ≤ |e| ≤ 10), which means that scientists are interested in the value of impact of infection e to the segment of DNA strand from position l to position r, inclusive.

第一行包含字符串 $s$（$1 \leq |s| \leq 10^5$），用于描述初始的 DNA 链。该字符串仅由大写英文字母 "A"、"T"、"G" 和 "C" 组成。

第二行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 表示事件的数量。

随后是 $q$ 行，每行描述一个事件。每行具有以下两种格式之一：

• 1 x c，其中 $x$ 是一个整数（$1 \leq x \leq |s|$），$c$ 是字母 "A"、"T"、"G" 或 "C"，表示 DNA 发生一次修改：位置 $x$ 处的核苷酸被更改为 $c$。
• 2 l r e，其中 $l$、$r$ 是整数（$1 \leq l \leq r \leq |s|$），$e$ 是由字母 "A"、"T"、"G" 和 "C" 组成的字符串（$1 \leq |e| \leq 10$），表示科学家希望计算感染序列 $e$ 对 DNA 链从位置 $l$ 到位置 $r$（含端点）这一区间的“影响值”。

For each scientists' query (second type query) print a single integer in a new line — the value of impact of the infection on the DNA.

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

Consider the first example. In the first query of second type all characters coincide, so the answer is 8. In the second query we compare string "TTTTT..." and the substring "TGCAT". There are two matches. In the third query, after the DNA change, we compare string "TATAT..."' with substring "TGTAT". There are 4 matches.

考虑第一个样例。在第二个类型的第一次查询中，所有字符均相同，因此答案为 $8$。在第二次查询中，我们将字符串 "TTTTT..." 与子串 "TGCAT" 进行比较，其中有 $2$ 个匹配。在第三次查询中，DNA 发生变化后，我们将字符串 "TATAT..." 与子串 "TGTAT" 进行比较，其中有 $4$ 个匹配。