Problem Background

Having weathered the storm, Little Soup has come to cherish everything even more. He believes that all things hold significant meaning for him. To ensure that he can remember them vividly, Little Soup decides to record them using certain methods.

Problem Description

Little Soup has recorded \( n \) meaningful items during this period, representing each with a string \( s_i \) and defining its value \( a_i \). Next, Little Soup will perform \( m \) operations.

• Operation 1: Little Soup will add a constant \( k \) to all \( a_i \) within the interval \( [l, r] \).
• Operation 2: Little Soup will set all \( a_i \) within the interval \( [l, r] \) to a constant \( k \).
• Operation 3: Little Soup provides a memory, which forms a string \( S \), and wants to determine the significance of \( S \) within the interval \( [l, r] \). Define \( cnt_i \) as the number of occurrences of \( s_i \) in \( S \), then the significance of \( S \) within the interval \( [l, r] \) is \( \sum_{i=l}^r cnt_i \times a_i \).

Input Format

The first line contains two numbers, \( n \) and \( m \).

The next \( n \) lines, the \( i \)-th line contains a string \( s_i \) and a number \( a_i \).

The next \( m \) lines each describe an operation, starting with three numbers, \( op \), \( l \), and \( r \). \( op \) represents the type of operation. If \( op = 3 \), an additional string \( S \) is input; otherwise, an additional number \( k \) is input.

Output Format

For each operation of type \( 3 \), output a number representing the total value.

Sample Input and Output

Input Sample #1

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

Output Sample #1

5
6

Input Sample #2

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

Output Sample #2

7
5
14
13

Input Sample #3

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

Output Sample #3

8
28

Notes

Sample 1 Explanation

For the first query, \( s_1 \) appears once, contributing \( 1 \) to the value; \( s_2 \) appears once, contributing \( 2 \) to the value; \( s_3 \) appears twice, contributing \( 2 \) to the value, totaling \( 5 \).

For the second query, \( s_1 \) appears twice, contributing \( 4 \) to the value; \( s_2 \) appears once, contributing \( 2 \) to the value, totaling \( 6 \).

Data Range

For \( 100\% \) of the data, \( 1 \le n, m \le 3 \times 10^4 \), \( k \ge 1 \), \( \sum |S|, \sum |s| \le 2 \times 10^5 \), and at all times \( 1 \le a_i \le 2 \times 10^4 \). Only characters \( a, b, c \) will be used.

见题面 Input 部分

见题面 Output 部分