「RdOI R2」风雨(rain)

经历过风雨的洗礼，小 Soup 才更懂得珍惜。他认为所有的一切对他来说都有重要的意义。为了能让这一切被自己牢牢铭记，小 Soup 决定用一些手段将它们记录下来。 [$\text\color{white}{真正的题目背景}$](https://z3.ax1x.com/2021/03/29/c9xbLj.gif)

小 Soup 在这段时间中记录了 $n$ 个有意义的东西，他把它们用字符串表示了出来，第 $i$ 个东西被表示成 $s_i$，并定义了它的价值 $a_i$。下面，小 Soup 会进行 $m$ 次操作。 操作 $1$：小 Soup 将区间 $l,r$ 里的 $a_i$ 都加上一个常数 $k$。 操作 $2$：小 Soup 将区间 $l,r$ 里的 $a_i$ 都赋值成一个常数 $k$。 操作 $3$：小 Soup 给出了一段回忆，这段回忆形成了一个字符串 $S$，他想求 $S$ 在区间 $l,r$ 中的意义有多大。定义 $cnt_i$ 为 $s_i$ 在 $S$ 中的出现次数，则 $S$ 在区间 $l,r$ 中的意义为 $\sum\limits_{i=l}^r cnt_i\times a_i$。

第一行两个数，$n,m$。 接下来 $n$ 行第 $i$ 行一个字符串 $s_i$ 和一个数 $a_i$。 接下来 $m$ 行每行一个操作，先有三个数，$op,l,r$。其中 $op$ 代表操作类型。$op=3$ 时，多输入一个字符串 $S$，否则多输入一个数 $k$。

对于每个 $3$ 操作输出一个数，代表总价值。

3 4
ab 1
ba 2
a 1
3 1 3 aba
1 1 2 1
2 2 3 2
3 1 2 abab

5
6

6 6
aba 3
ba 2
aa 2
c 1
abac 4
ab 2
3 2 5 abac
2 3 5 3
3 4 6 abc
1 2 3 1
3 1 3 aabaa
3 2 5 aabac

7
5
14
13

6 3
b 1
aa 8
cc 9
cac 8
ab 10
a 7
2 1 3 2
3 1 4 acac
3 1 6 ccaba

8
28

**样例 $1$ 解释** 对于第一次询问，$s_1$ 出现了 $1$ 次，对价值贡献为 $1$；$s_2$ 出现了 $1$ 次，对价值贡献为 $2$；$s_3$ 出现了 $2$ 次，对价值贡献为 $2$，总价值为 $5$。 对于第二次询问，$s_1$ 出现了 $2$ 次，对价值贡献为 $4$；$s_2$ 出现了 $1$ 次，对价值贡献为 $2$，总价值为 $6$。 --- **数据范围** |数据编号|$\sum s,\sum S$|$n,m$|特殊性质| |:---:|:---:|:---:|:---:| |$1\sim 2$|$\le5\times10^3$|$10^3$|$\diagdown$| |$3\sim 4$|$\le2\times 10^5$|$3\times10^4$|没有 $1$ 操作| |$5\sim 8$|$\le2\times 10^5$|$3\times10^4$|没有 $1,2$ 操作| |$9\sim 13$|$\le2\times 10^5$|$3\times10^4$| $\diagdown$| 对于 $100\%$ 的数据，$1\le n,m\le3\times10^4,k\ge 1,\sum |S|,\sum |s|\le2\times10^5$，任何时刻 $1\le a_i\le2\times10^4$，保证只会出现 $a,b,c$ 三种字符。