题目描述

Y 同学维护一个只含小写英文字母的字符串 $s$。系统会进行两类操作：第一类把某个位置的字符修改为给定字符；第二类给出区间 $[l,r]$ 和模式串 $p$，询问 $p$ 在子串 $s_l s_{l+1}\dots s_r$ 中出现了多少次。

出现可以重叠。例如 aaa 中 aa 出现两次。所有位置均按 $1$ 下标计数。修改会影响之后的所有询问。

直接对每次询问重新匹配会被大量短模式和长区间卡住。请你按顺序处理全部操作并输出每个询问的答案。

输入格式

第一行包含字符串 $s$。

第二行包含整数 $q$。

接下来 $q$ 行，每行形如 1 i c 或 2 l r p，分别表示修改和询问。

输出格式

对每个询问操作输出一行一个整数。

样例

样例输入 #1

ababa
4
2 1 5 aba
1 3 c
2 1 5 aba
2 2 5 ba

样例输出 #1

2
0
1

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le |s|,q\le10^5$，所有询问模式串非空，所有询问模式串总长度不超过 $10^5$。

特殊性质 A：保证没有修改操作。 特殊性质 B：保证所有模式串长度为 $1$。