3954: 【NOIP2022赛前】T4

#### 题目描述

现在是晚上九点，小王准备为大家献歌一首。

小王要唱的歌的歌词可以抽象成一个长度为 $n$ 的字符串 $s$ ，**其中每个字符可能是大小写字母，数字，下划线。**

(注：大小写相同字母视为不同的字符)

现在，小Q会进行以下 $m$ 次操作，每次操作给定 $l, r, t$ :

1. 小Q为了让小王唱的更魔怔，把歌词的第 $l$ 个字符到第 $r$ 个字符替换为长度为 $r-l+1$ 的字符串 $t$ 。
2. 小Q想检验小王唱的怎么样，让小王从第 $l$ 个字符唱到第 $r$ 个字符。他想知道在这个过程他总共会 听到多少次 $t$ 。即 $t$ 在 $s[l, r]$ 中共可重叠出现了多少次。

由于训练小王唱歌不是一件轻松的事，所以小Q请你写一个程序来帮他训练小王并回答每次询问。

#### 输入格式

第一行两个整数 $n, m$ 。

接着一行长度为 $n$ 的字符串 $s$ 。

下面 $m$ 行每行开头一个 $1$ 或 $2$ 表示操作类型，然后是两个正整数 $l, r$ 和一个字符串 $t$ 。

#### 输出格式


对于每次 2 操作，输出一行表示答案。

#### 输入样例1

```
34 10
JinWan9Dian_WHQChangGe_BuJianBuSan
2 1 34 an
2 6 33 an
1 1 10 aaaaaaaaaa
2 2 9 aaa
2 1 34 _
1 11 20 abaabaabab
2 1 20 ab
2 1 20 aab
1 1 34 JinWan9Dian_WHQChangGe_BuJianBuSan
2 1 34 JinWan9Dian_WHQChangGe_BuJianBuSan
```

#### 输出样例1

```
5
3
6
2
4
3
1
```

#### 数据范围

| 测试点编号 | $n,m\leq$      | $k_1\leq$      | $k_2\leq$      |
| :--------- | :------------- | :------------- | :------------- |
| $1∼4$      | $5\times 10^3$ | $5\times 10^3$ | $5\times 10^3$ |
| $5∼7$      | $10^5$         | $0$            | $10^5$         |
| $8∼12$     | $5\times 10^4$ | $5\times 10^4$ | $5\times 10^4$ |
| $12∼15$    | $10^5$         | $10^5$         | $10^5$         |
| $16∼20$    | $10^5$         | $2\times 10^6$ | $10^5$         |

其中， $k_1$ 为所有 1 操作中的 $t$ 长度之和， $k_2$ 为所有 2 操作中的 $t$ 长度之和。

提示：此题并不难。