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!
## Input
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.
## Output
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.
[samples]
## Note
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.
众所周知，DNA链由核苷酸组成。共有四种核苷酸："_A_"、"_T_"、"_G_"、"_C_"。DNA链是核苷酸的序列。科学家们决定追踪一种稀有物种的进化过程，该物种的DNA链初始时为字符串 #cf_span[s]。
该物种的进化过程描述为DNA的一系列变化。每次变化是某个核苷酸的改变，例如，在DNA链"_AAGC_"中，第二个核苷酸可以变为"_T_"，从而得到新的DNA链"_ATGC_"。
科学家们知道，DNA链的某些片段可能受到某种未知感染的影响。他们将感染表示为一个核苷酸序列。科学家们关心是否存在由某些感染引起的变化。因此，他们有时需要计算某个感染对DNA某段的影响值。该值的计算方式如下：
作为一名开发者，Innokenty也对生物信息学感兴趣，因此科学家们向他寻求帮助。但Innokenty正忙于准备VK Cup，于是他决定将这个问题委托给参赛者。请帮助科学家们！
第一行包含字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 10^5]），描述初始的DNA链。它仅由大写英文字母"_A_"、"_T_"、"_G_"和"_C_"组成。
第二行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 10^5]）——事件的数量。
随后有 #cf_span[q] 行，每行描述一个事件。每行具有以下两种格式之一：
对于每个科学家的查询（第二种类型的查询），请在新行中输出一个整数——该感染对DNA的影响值。
考虑第一个例子。在第一个第二种类型查询中，所有字符都相同，因此答案为 #cf_span[8]。在第二个查询中，我们比较字符串"_TTTTT..._"和子串"_TGCAT_"。有两个匹配。在第三个查询中，DNA改变后，我们比较字符串"_TATAT..._"与子串"_TGTAT_"。有 #cf_span[4] 个匹配。
## Input
第一行包含字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 10^5]），描述初始的DNA链。它仅由大写英文字母"_A_"、"_T_"、"_G_"和"_C_"组成。第二行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 10^5]）——事件的数量。随后有 #cf_span[q] 行，每行描述一个事件。每行具有以下两种格式之一：
_1 x c_，其中 #cf_span[x] 是整数（#cf_span[1 ≤ x ≤ |s|]），#cf_span[c] 是字母"_A_"、"_T_"、"_G_"或"_C_"，表示DNA发生一次变化：位置 #cf_span[x] 的核苷酸现在为 #cf_span[c]。
_2 l r e_，其中 #cf_span[l]、#cf_span[r] 是整数（#cf_span[1 ≤ l ≤ r ≤ |s|]），#cf_span[e] 是由字母"_A_"、"_T_"、"_G_"和"_C_"组成的字符串（#cf_span[1 ≤ |e| ≤ 10]），表示科学家们希望计算感染 #cf_span[e] 对DNA链从位置 #cf_span[l] 到位置 #cf_span[r]（包含两端）的片段的影响值。
## Output
对于每个科学家的查询（第二种类型的查询），请在新行中输出一个整数——该感染对DNA的影响值。
[samples]
## Note
考虑第一个例子。在第一个第二种类型查询中，所有字符都相同，因此答案为 #cf_span[8]。在第二个查询中，我们比较字符串"_TTTTT..._"和子串"_TGCAT_"。有两个匹配。在第三个查询中，DNA改变后，我们比较字符串"_TATAT..._"与子串"_TGTAT_"。有 #cf_span[4] 个匹配。
**Definitions**
Let $ s \in \{A, T, G, C\}^* $ be the initial DNA string.
Let $ q \in \mathbb{Z}^+ $ be the number of events.
Let $ I \in \{A, T, G, C\}^* $ be the infection pattern, initially $ I = s $ (but updated by type-1 events).
**Constraints**
1. $ 1 \le |s| \le 10^5 $
2. $ 1 \le q \le 10^5 $
3. Each event is one of:
- Type 1: `1 i c` — update $ s[i] \leftarrow c $, where $ i \in \{1, \dots, |s|\} $, $ c \in \{A, T, G, C\} $
- Type 2: `2 l r` — compute impact of infection $ I = s $ on substring $ s[l:r+1] $, where $ 1 \le l \le r \le |s| $
**Objective**
For each type-2 query `2 l r`:
Compute the number of positions $ j \in \{0, 1, \dots, r-l\} $ such that:
$$
s[l + j] = s[j + 1]
$$
That is, count the number of matching nucleotides between the substring $ s[l:r+1] $ and the prefix $ s[1:r-l+1] $ of the same length.
Formally:
$$
\text{Impact}(l, r) = \sum_{j=0}^{r-l} \mathbf{1}_{s[l + j] = s[j + 1]}
$$