Memorable Operations

Little Soup recorded \(n\) meaningful items, where the \(i\)-th item is represented by a string \(s_i\) with an associated value \(a_i\). He then performs \(m\) operations. There are three types of operations:

1. Operation 1: For an interval \([l, r]\), add a constant \(k\) to each \(a_i\). That is, \(a_i = a_i + k\) for all \(l \le i \le r\).
2. Operation 2: For an interval \([l, r]\), set each \(a_i\) to a constant \(k\). That is, \(a_i = k\) for all \(l \le i \le r\).
3. Operation 3: Given a memory in the form of a string \(S\), let \(cnt_i\) denote the number of (possibly overlapping) occurrences of \(s_i\) in \(S\). The significance of the memory over the interval \([l, r]\) is defined as \[ \sum_{i=l}^{r} cnt_i \times a_i, \] and you are asked to compute this value.

For each Operation 3, output the computed significance on a separate line.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\), where \(n\) is the number of items and \(m\) is the number of operations.

The next \(n\) lines each contain a string and an integer separated by space, representing \(s_i\) and \(a_i\) respectively.

The following \(m\) lines each represent an operation in one of the following formats:

• Operation 1: 1 l r k (add \(k\) to all \(a_i\) for \(l \le i \le r\))
• Operation 2: 2 l r k (set all \(a_i\) for \(l \le i \le r\) to \(k\))
• Operation 3: 3 l r S (compute \(\sum_{i=l}^{r} cnt_i \times a_i\), where \(cnt_i\) is the count of \(s_i\) in the string \(S\))

It is guaranteed that the values \(l\) and \(r\) are valid (1-indexed).

outputFormat

For each Operation 3, output a single line containing the computed significance value.

sample

3 4
apple 5
banana 3
cat 2
3 1 2 applebanana
1 1 3 3
3 2 3 bananacat
2 1 1 10

8
11