Eftir valið í héraðsliðið féll White í langt tímabil vonbrigða. Hún gat ekki fundið neina von í niðurstöðum sínum. Engu að síður hélt White áfram lokaæfingum sínum fyrir NOI. Auk hefðbundinna æfinga byrjaði hún einnig að kanna viðfangsefni sem hún hafði aldrei haft tækifæri til að læra á OI-árum sínum — í þeirri von að áður en hún kveddi yrði engin eftirsjá lengur.

White hristi af sér reikular hugsanir og einbeitti sér skyndilega að verkefni fyrir framan sig, einföldu og leiðinlegu gagnagrindaverkefni —

White er með runu af $n$ heiltölum $a_1, a_2, \dots, a_n$. Hún mun framkvæma $q$ aðgerðir á þessa runu. Hver aðgerð er af einni af eftirfarandi þremur gerðum:

• 1 l r v — Bæta $v$ við hvert stak á bilinu $[l, r]$.
• 2 l r v — Setja hvert stak á bilinu $[l, r]$ sem $v$.
• 3 l r — Spyrja um gildið $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ módulo $2^{64}$.

Verkefni þitt er að herma allar aðgerðirnar og skrifa út niðurstöður allra fyrirspurna.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $n, q$ ($1 \le n, q \le 2 \times 10^5$), sem tákna fjölda staka og fjölda aðgerða.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), sem tákna upphaflegu stökin.

Hver af næstu $q$ línum lýsir aðgerð á einu af þremur sniðum:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), sem táknar samlagningaraðgerð.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), sem táknar gildisveitingaraðgerð.
• 3 l r ($1 \le l \le r \le n$), sem táknar fyrirspurnaraðgerð.

Tryggt er að $0 \le a_i \le 10^9$ fyrir hvert $1 \le i \le n$ í gegnum allt ferlið.

Úttak

Fyrir hverja fyrirspurnaraðgerð skaltu prenta heiltölu í einni línu — niðurstöðu fyrirspurnarinnar módulo $2^{64}$.

Dæmi

Inntak

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

Úttak

35
39
40
34
177
120

Inntak

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

Úttak

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

Athugasemd

Í fyrsta prófunartilvikinu:

Upphaflega runan er 2 3 5 4 1. Eftir þriðju aðgerðina verður hún 2 3 2 2 1, og eftir sjöttu aðgerðina verður hún 7 8 7 7 6.

Fyrir fyrstu fyrirspurnina er svarið $\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$.

Fyrir aðra fyrirspurnina er svarið $\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$.