题目描述

圆滑博士不仅是字符串大师，也是数据结构大师，这次他给他的学生们出了一道新题目。他给出了两个字符串 $S$ 和 $T$，它们都由大写字母组成。任务是编写一个高效的程序来处理这些字符串上的操作和查询。

1. 操作 $C \ i \ ch$: 给定整数 $i$ 和大写字母 $ch$，该操作将字符串 $S$ 中的第 $i$ 个字符修改为 $ch$。
2. 查询 $Q \ i \ j$: 给定整数 $i$ 和 $j$，该查询要求程序找出字符串 $S$ 的第 $i$ 个字符到第 $j$ 个字符之间的子串（即 $\overline{s_is_{i + 1}\cdots s_j}$）中，字符串 $T$ 出现的总次数。

圆滑博士希望程序运行得又快又好，能够处理大字符串和大量查询或操作。

输入格式

1. 第一行包含一个整数 $N$ ($1 \leq N \leq 10^5$)，表示操作或查询的数量。
2. 第二行是字符串 $S$ ($|S| \leq 10^5$)。
3. 第三行是字符串 $T$ ($|T| \leq 10$)。
4. 接下来的 $N$ 行中，每行要么是一个操作，要么是一个查询，按照上面描述的格式给出。

题目保证：$|T| \leq |S|$，且查询操作合法，即操作位置均满足 $1 \leq i \leq |S|$，修改字符为大写字符，查询操作满足 $1\leq i \leq j \leq |S|$。

输出格式

对于每次询问，一行包含一个整数，表示字符串 $T$​ 出现的总次数。

样例

5
AABBABA
AA
Q 1 3
C 6 A
Q 2 7
C 2 B
Q 1 5

1
2
0

数据范围

对于 $20\%$ 的数据满足 $1 \leq N \leq 10^3$， $|S| \leq 10^3$。

对于 $100\%$ 的数据满足输入格式中的约束。