Background

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}

Problem Description

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$.

Input Format

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.

Output Format

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

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

Hint

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

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