Etter uttaket til provinslaget falt White inn i en lang periode med skuffelse. Hun klarte ikke å finne noe håp i resultatene sine. Likevel fortsatte White den siste treningen før NOI. I tillegg til den vanlige treningen begynte hun også å utforske emner hun aldri hadde hatt sjansen til å lære i løpet av OI-dagene sine — i håp om at det, før hun tok farvel, ikke ville være noe mer å angre på.

White ristet av seg de vandrende tankene og fokuserte plutselig på et problem foran seg, et enkelt og kjedelig datastrukturproblem —

White har en følge av $n$ heltall $a_1, a_2, \dots, a_n$. Hun vil utføre $q$ operasjoner på denne følgen. Hver operasjon er av én av følgende tre typer:

• 1 l r v — Legg til $v$ til hvert element i intervallet $[l, r]$.
• 2 l r v — Sett hvert element i intervallet $[l, r]$ til $v$.
• 3 l r — Spør om verdien $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ modulo $2^{64}$.

Din oppgave er å simulere alle operasjoner og skrive ut resultatene av alle spørringer.

Inndata

Den første linjen i inndataene inneholder to heltall $n, q$ ($1 \le n, q \le 2 \times 10^5$), som representerer antall elementer og antall operasjoner.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), som representerer startelementene.

Hver av de neste $q$ linjene beskriver en operasjon, i ett av de tre formatene:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), som representerer addisjonsoperasjonen.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), som representerer tilordningsoperasjonen.
• 3 l r ($1 \le l \le r \le n$), som representerer spørreoperasjonen.

Det garanteres at $0 \le a_i \le 10^9$ for hver $1 \le i \le n$ gjennom hele prosessen.

Utdata

For hver spørreoperasjon skal du skrive ut et heltall på én enkelt linje — resultatet av spørringen modulo $2^{64}$.

Eksempler

Inndata

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

Inndata

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

Forklaring

I det første testtilfellet:

Den opprinnelige følgen er 2 3 5 4 1. Etter den tredje operasjonen blir den 2 3 2 2 1, og etter den sjette operasjonen blir den 7 8 7 7 6.

For den første spørringen er 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$.

For den andre spørringen er 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$.