Problem Description

You need to maintain a sequence \( A \) of \( n \) elements and perform \( m \) operations:

• 1 l r x: Add \( x \) to all numbers in the interval \([l, r]\).
• 2 l r x: Multiply all numbers in the interval \([l, r]\) by \( x \).
• 3 l r: Output the sum \( S \) of all numbers in the interval \([l, r]\) modulo \( 19260817 \).
• 4: Revert the sequence \( A \) to the state before the last 4 operation (or to the initial state if there was no previous 4 operation), and then reverse the order of execution for all 1 and 2 operations performed since the last revert.

Input Format

The first line contains two positive integers \( n \) and \( m \).
The second line contains \( n \) integers representing the initial state of \( A \).
The next \( m \) lines describe the \( m \) operations as per the problem description.

Output Format

For each 3 operation, output a positive integer followed by a newline.

Sample Input and Output

Input Sample #1

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

Output Sample #1

39
33

Input Sample #2

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

Output Sample #2

31

Input Sample #3

7 14
305 740 36 205 343 20 90 
4
2 2 7 529
3 1 2
1 2 4 713
4
3 3 7
3 2 4
4
1 6 7 597
1 1 4 232
3 2 4
1 1 3 220
3 1 7
4

Output Sample #3

391765
1121480
1650480
521784
763812

Notes

Sample Explanation:

Sample 1

1. Initial state: 1 2 3 4 5
2. 1 1 3 3 -> Sequence becomes 4 5 6 4 5
3. 2 2 4 2 -> Sequence becomes 4 10 12 8 5
4. 3 1 5 -> Sum is \( 4 + 10 + 12 + 8 + 5 = 39 \)
5. 4 -> Revert to initial state 1 2 3 4 5, then execute 2 2 4 2 and 1 1 3 3 in reverse -> Sequence becomes 4 7 9 8 5
6. 3 1 5 -> Sum is \( 4 + 7 + 9 + 8 + 5 = 33 \)

Sample 2

1. Initial state: 1 1 1 1 1
2. 1 1 3 1: 2 2 2 1 1
3. 2 2 4 2: 2 4 4 2 1
4. 4: 2 3 3 2 1
5. 1 1 5 1: 3 4 4 3 2
6. 2 1 5 2: 6 8 8 6 4
7. 4: Revert to 2 4 4 2 1 and execute 2 1 5 2 -> 1 1 5 1: 5 9 9 5 3
8. 3 1 5 2 Answer is \( 31 \)

Data Range

For the first \( 10\% \) of the data, there are no 4 operations.
For the first \( 30\% \) of the data, \( n, m \le 10^3 \).
For the first \( 50\% \) of the data, the space limit is \( 400 \) MB, and for the other \( 50\% \), the space limit is \( 45 \) MB.
For \( 100\% \) of the data, \( 1 \le n \le 5 \times 10^5 \), \( 0 \le A_i, x \le 10^3 \), \( 1 \le m \le 10^5 \).
The time limit is \( 500 \) ms.

见题面 Input 部分

见题面 Output 部分