Efter uttagningen till provinslaget föll White in i en lång period av besvikelse. Hon kunde inte finna något hopp i sina resultat. Trots det fortsatte White sin sista träning inför NOI. Utöver sin vanliga träning började hon också utforska ämnen som hon aldrig hade haft chansen att lära sig under sina OI-dagar — i hopp om att det, innan hon tog farväl, inte skulle finnas något mer att ångra.

White skakade av sig sina vandrande tankar och fokuserade plötsligt på ett problem framför sig, ett enkelt och tråkigt datastrukturproblem —

White har en talföljd av $n$ heltal $a_1, a_2, \dots, a_n$. Hon kommer att utföra $q$ operationer på denna talföljd. Varje operation är av en av följande tre typer:

• 1 l r v — Addera $v$ till varje element i intervallet $[l, r]$.
• 2 l r v — Tilldela varje element i intervallet $[l, r]$ värdet $v$.
• 3 l r — Fråga efter värdet $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ modulo $2^{64}$.

Din uppgift är att simulera alla operationer och skriva ut resultaten av alla frågor.

Indata

Den första raden i indatan innehåller två heltal $n, q$ ($1 \le n, q \le 2 \times 10^5$), som representerar antalet element och antalet operationer.

Den andra raden innehåller $n$ heltal $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), som representerar de ursprungliga elementen.

Var och en av de följande $q$ raderna beskriver en operation i ett av de tre formaten:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), som representerar additionsoperationen.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), som representerar tilldelningsoperationen.
• 3 l r ($1 \le l \le r \le n$), som representerar frågeoperationen.

Det garanteras att $0 \le a_i \le 10^9$ för varje $1 \le i \le n$ under hela processen.

Utdata

För varje frågeoperation, skriv ut ett heltal på en egen rad — resultatet av frågan modulo $2^{64}$.

Exempel

Indata

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

Utdata

35
39
40
34
177
120

Indata

10 20
1 2 3 4 5 6 7 8 9 10
1 1 10 1
3 1 5
3 2 9
3 8 10
1 2 5 10
3 1 5
3 2 9
3 8 10
1 5 9 -5
3 1 5
3 2 9
3 8 10
1 2 5 -10
3 1 5
3 2 9
3 8 10
1 5 9 5
3 1 5
3 2 9
3 8 10

Utdata

40
156
270
120
1202
270
118
831
80
33
61
80
40
156
270

Förklaring

I det första testfallet:

Den ursprungliga talföljden är 2 3 5 4 1. Efter den tredje operationen blir den 2 3 2 2 1, och efter den sjätte operationen blir den 7 8 7 7 6.

För den första frågan är svaret $\sum_{i=1}^5 (\min_{j=1}^i a_j) \times (\max_{j=1}^i a_j) = 2 \times 2 + 2 \times 3 + 2 \times 5 + 2 \times 5 + 1 \times 5 = 35$.

För den andra frågan är svaret $\sum_{i=2}^4 (\min_{j=2}^i a_j) \times (\max_{j=2}^i a_j) = 3 \times 3 + 3 \times 5 + 3 \times 5 = 39$.