Problem Description

QinQin has given you two sequences \(a\) and \(b\), each of length \(n\). You need to support three types of operations, totaling \(m\) times:

1. 1 l r x, modify all numbers in the interval \([l, r]\) of sequence \(a\) to \(x\).
2. 2 l r y, modify all numbers in the interval \([l, r]\) of sequence \(b\) to \(y\).
3. 3 l r, compute \(\sum_{i=l}^r \sum_{j=1}^{b_i} a_j\). The answer should be taken modulo \(2^{32}\).

Input Format

The input consists of integers.

• The first line contains two numbers \(n\) and \(m\).
• The second line contains \(n\) numbers representing sequence \(a\).
• The third line contains \(n\) numbers representing sequence \(b\).
• The next \(m\) lines, each describing an operation as specified in the problem description.

Output Format

For each operation of type 3, output one integer per line representing the answer.

Sample Input and Output

Input Sample #1

4 5
5 5 4 5
3 4 4 1
2 3 3 2
2 2 3 4
3 1 4
1 3 3 2
3 2 4

Output Sample #1

57
39

Input Sample #2

5 5
1 7 5 2 5
2 1 5 3 2
1 5 5 3
1 3 5 2
3 1 4
2 1 4 2
3 1 3

Output Sample #2

33
24

Input Sample #3

10 10
27 29 12 16 16 6 20 22 17 1
2 6 1 10 4 1 3 10 9 6
2 3 5 6
3 2 10
2 5 10 9
3 5 9
1 1 5 24
1 6 10 12
3 2 3
1 4 6 14
1 4 8 14
3 5 10

Output Sample #3

956
825
264
924

Notes

This problem uses batched tests.

Note: The original time limit was 5 seconds, but it was too tight, so it was changed to 7 seconds by the administrators.

For 100% of the data, \(1 \le n \le 5 \times 10^5\), \(1 \le m \le 3 \times 10^5\), \(1 \le a_i, x \le 10^9\), \(1 \le b_i, y \le n\).

见题面 Input 部分

见题面 Output 部分