Description

给定一个长为 $n$ 的字符串 $S$，$Q$ 次操作，共两种形式：

1. 给定 $p,c$，将 $S_p$ 修改为 $c$；
2. 给定 $l,r,t$，查询 $S_{l\cdots r}$ 中，字符串 $t$ 作为子串出现的次数。

Constraints and Subtasks

对于全部测试点，满足：

• $n \le 1\times 10^5$
• $Q \le 2\times 10^6$
• $\sum |t| \le 1\times 10^5$
• 所有字符串中的字符均为小写字母，或者说，它们的 ASCII 码在 $97$ 和 $122$ 之间。

另外，还有一些测试点满足特殊要求。

Input

输入内容从标准输入中给出，格式如下：

$ \boxed{\begin{aligned} & S \\ & Q \\ & \text{operator}_1 \\ & \text{operator}_2 \\ & ~ \vdots \\ & \text{operator}_Q \end{aligned}} $

其中，每个 $\text{operator}$ 有两种类型：

1. $\boxed{1 {\quad} p {\quad} c}$：表示第一种操作，将 $S_p$ 修改为 $c$；
2. $\boxed{2 {\quad} l {\quad} r {\quad} t}$：表示第二种操作，查询 $S_{l\cdots r}$ 中，字符串 $t$ 作为子串出现的次数。

Output

对于每个第二类的操作（即询问），输出一行一个整数表示答案。

Sample

acabababaaabaab
3
2 1 10 aba
1 4 c
2 2 8 aba

3
1