#1436. [L3-1] Dracu-Riot!

海上都市——一座特别的岛屿，作为特别行政区，是个风俗和赌博合法化的欢乐都市。但实际上，是政府唯一认可吸血鬼所居住的场所。

佑斗和好友直太第一天登岛就遇见了绑架事件，阴差阳错下，佑斗感染了吸血鬼病毒，变成了吸血鬼，只能被迫留在岛上。

按照规定，吸血鬼必须为岛上的服务业进行有偿劳动，所以佑斗加入了风纪班，负责岛上的安保工作。

最近，佑斗、美羽、梓三人缴获一批走私品，被他们的上司兵馬要求在出入境名单中检索一些嫌疑人，以便观察其是否有某一时段内多次出入境行为。

不幸的是，海关的系统近期在维护，所以出现一个很大的问题：导出的名单只显示输入的字母，并且分隔符消失了。

更不幸的是，兵馬告诉他们，由于系统出现了问题，可能需要对记录中的某个子串进行修改。

三人没有办法，他们找到你，希望你能写一个程序帮助他们完成这个任务。

形式化地，系统记录名单 $S$ 和要查找的名字 $T_i$ 将是由小写字母组成的字符串。字符串下标从 $1$ 开始标号。

接下来有 $Q$ 次操作，操作分为两种：

$1\ l_i\ r_i\ p_i$：你需要计算 $T_{p_i}$ 串在 $S$ 串的子串 $S[l_i:r_i]$ 内出现了多少次。

$2\ l_i\ r_i\ s_i$：修改 $S$ 串的子串 $S[l_i:r_i]$ 为 $s_i$。

特别地，类似梓的名字 azusa 在 azusazusazusa 算作出现 $3$ 次，即字符串发生重叠也要重复计算。

第 $1$ 行是一个由小写字母组成的字符串 $S$，作为系统记录名单。

第 $2$ 行是一个正整数 $D$，表示嫌疑人名单的长度。

接下来 $D$ 行每行是一个由小写字母组成的字符串 $T_i$，作为要查找的姓名。

第 $D+3$ 行是一个正整数 $Q$，表示接下来要进行 $Q$ 次操作。

接下来 $Q$ 行对操作进行描述：

对于 $1$ 操作，形如 $1\ l_i\ r_i\ p_i$，你需要计算 $T_{p_i}$ 串在 $S$ 串的子串 $S[l_i:r_i]$ 内出现了多少次。

对于 $2$ 操作，形如 $2\ l_i\ r_i\ s_i$，修改 $S$ 串的子串 $S[l_i:r_i]$ 为 $s_i$。

对于每次 $1$ 操作，输出 $T_{p_i}$ 串出现次数。

输入

namanamazunamanamakonamanameko
4
am
name
august
key
10
1 1 30 2
2 5 10 mamama
2 7 12 nanami
1 6 18 1
2 15 21 banamam
2 25 30 meguru
1 2 27 1
2 4 20 yoshinosaysciallo
1 5 30 1
1 1 30 4

输出

1
2
7
2
0

对于 $30\%$ 的数据：

$|S|,Q\le 10^3$，$|s_i|\le 10$，$D=1$。

对于 $100\%$ 的数据：

$|S|,Q\le 10^5$，$|T_i|\le 20$，$D\le 500$，

$|s_i|\le |S|$，对于 $2$ 操作，$\sum |s_i|\le 10^6$，

$1\le l_i\le r_i\le |S|$，$|s_i|=r_i-l_i+1$，$1\le p_i\le D$，

保证 $S,T_i,s_i$ 由小写字母组成，字符串长度至少为 $1$。

保证 $T_i$ 互不相同。