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