Background

Recently, a mysterious ring appeared on the Moon.

It is said that as long as you get this ring, you can travel through time and space……

Problem Description

You need to maintain a sequence $A$ with $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 value of $S \bmod 19260817$, where $S$ is the sum of all numbers in the interval $[l,r]$.

• 4: roll back the sequence $A$ to the state before the previous 4 operation (if there is no previous one, roll back to the initial state), and at the same time execute in reverse order all 1 and 2 operations from after the previous rollback to before this rollback (see the sample explanation).

Input Format

The first line contains two positive integers $n,m$.

The second line contains $n$ integers, representing the initial state of $A$.

Lines $3$ to $m+2$ contain $m$ operations. The format is described above.

Output Format

For each operation 3, output one positive integer per line.

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

39
33

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

31

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

391765
1121480
1650480
521784
763812

Hint

Sample Explanation

1

1. Initial state: 1 2 3 4 5.
2. 1 1 3 3 -> the sequence becomes 4 5 6 4 5.
3. 2 2 4 2 -> the sequence becomes 4 10 12 8 5.
4. 3 1 5 -> $ans=4+10+12+8+5=39$.
5. 4 -> roll back to the initial state 1 2 3 4 5 -> execute 2 2 4 2 and 1 1 3 3 in order -> the sequence becomes 4 7 9 8 5.
6. 3 1 5 -> $ans=4+7+9+8+5=33$.

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: roll back to 2 4 4 2 1 and execute 2 1 5 2 -> 1 1 5 1 in order: 5 9 9 5 3.
8. 3 1 5 2: the answer is $31$.

Constraints

For the first $10\%$ of the testdata, there is no operation 4.

For the first $30\%$ of the testdata, $n,m \le 10^3$.

For the first $50\%$ of the testdata, the memory limit is $400$ MB. For the other $50\%$ of the testdata, the memory limit is $45$ MB.

For $100\%$ of the testdata, $1 \le n \le 5 \times 10^5$, $0 \le A_i,x \le 10^3$, $1 \le m \le 10^5$.

d0j1a_1701 is a “shàn liáng” (kind-hearted) problem setter, so the time limit is $500$ ms.

Easter Egg

【Afterword】

Wearing the latest high-tech spacesuit, you land on the Moon.

The ring you have dreamed of is right in front of you.

You slowly walk toward it.

But the ring stretches out transparent barriers all around. Blue-green light spreads inside and covers you.

You float up. You can no longer tell whether you are controlling the ring, or the ring is controlling you.

Suddenly, a dazzling beam of light shines in. You instinctively close your eyes, and a whooshing sound fills your ears. You feel something like wind, but it is not ordinary wind.

Suddenly, the wind stops. Your feet are back on solid ground. Opening your hazy eyes, you see rin and len playing an absolutely simple game……

Translated by ChatGPT 5