P7582 「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$。

无

无

**样例 $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$ 三种字符。