给定一个字符串 s,处理 q 个查询,每个查询具有以下形式之一:
- 1 i c — 将字符串中的第 i 个字符更改为 c。
- 2 l r y — 考虑 s 的子字符串,从位置 l 开始,到位置 r 结束。输出 y 作为子字符串在其中出现的次数。
输入
输入的第一行包含小写英文字母的字符串 s (1 ≤ |s| ≤ 105)。
第二行包含一个整数 q (1 ≤ q ≤ 105) — 要处理的查询数。
接下来的 q 行描述查询,可能具有以下形式之一:
- 1 i c (1 ≤ i ≤ |s|)
- 2 l r y (1 ≤ l ≤ r ≤ |s|)
c 为小写英文字母,y 为仅由小写英文字母组成的非空字符串。
|y| 的总和所有第二类型的查询最多为 105。
保证至少有一个第二类型的查询。
所有字符串的索引都是 1。
|s|是字符串 s 的长度。
输出
对于类型 2 的每个查询,在单独的行中输出所需的答案。
示例
输入 #1
ababababa 3 2 1 7 aba 1 5 c 2 1 7 aba
输出 #1
3 1
输入 #2
abcdcbc 5 2 1 7 bc 1 4 b 2 4 7 bc 1 2 a 2 1 4 aa
输出 #2
2 2 1
注意
考虑第一个示例案例。最初,字符串 aba 在 [1, 7] 范围内出现 3 次。请注意,两次出现可能会重叠。
更新后,字符串变为 ababcbaba,现在 aba 在 [1, 7] 范围内仅出现一次。