D

题目描述

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

小王要唱的歌的歌词可以抽象成一个长度为 $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

数据范围

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