P7582 "RdOI R2" Storm and Rain (rain)

After being tempered by storms and rain, Little Soup knows better how to cherish things. He believes that everything has important meaning to him. To keep all of this firmly in his memory, Little Soup decides to use some methods to record them. [$\text\color{white}{The real background}$](https://z3.ax1x.com/2021/03/29/c9xbLj.gif)

During this period, Little Soup recorded $n$ meaningful things, and represented them with strings. The $i$-th thing is represented as $s_i$, and its value is defined as $a_i$. Next, Little Soup will perform $m$ operations. Operation 1: Little Soup adds a constant $k$ to all $a_i$ in the interval $[l, r]$. Operation 2: Little Soup assigns all $a_i$ in the interval $[l, r]$ to a constant $k$. Operation 3: Little Soup gives a memory, which forms a string $S$. He wants to know how meaningful $S$ is within the interval $[l, r]$. Let $cnt_i$ be the number of occurrences of $s_i$ in $S$. Then the meaning of $S$ in the interval $[l, r]$ is $\sum\limits_{i=l}^r cnt_i \times a_i$.

The first line contains two integers $n, m$. The next $n$ lines: the $i$-th line contains a string $s_i$ and an integer $a_i$. The next $m$ lines: each line describes one operation, starting with three integers $op, l, r$, where $op$ denotes the operation type. When $op = 3$, an additional string $S$ is given; otherwise, an additional integer $k$ is given.

For each operation of type $3$, output one integer, representing the total value.

**Sample 1 Explanation** For the first query, $s_1$ appears $1$ time and contributes $1$ to the value; $s_2$ appears $1$ time and contributes $2$; $s_3$ appears $2$ times and contributes $2$. The total value is $5$. For the second query, $s_1$ appears $2$ times and contributes $4$; $s_2$ appears $1$ time and contributes $2$. The total value is $6$. --- **Constraints** |Test ID|$\sum s, \sum S$|$n, m$|Special Property| |:---:|:---:|:---:|:---:| |$1 \sim 2$|$\le 5 \times 10^3$|$10^3$|$\diagdown$| |$3 \sim 4$|$\le 2 \times 10^5$|$3 \times 10^4$|No operation $1$| |$5 \sim 8$|$\le 2 \times 10^5$|$3 \times 10^4$|No operations $1, 2$| |$9 \sim 13$|$\le 2 \times 10^5$|$3 \times 10^4$|$\diagdown$| For $100\%$ of the testdata, $1 \le n, m \le 3 \times 10^4$, $k \ge 1$, $\sum |S|, \sum |s| \le 2 \times 10^5$. At any time, $1 \le a_i \le 2 \times 10^4$. It is guaranteed that only the three characters $a, b, c$ will appear. Translated by ChatGPT 5