Maakuntajoukkueen valintakokeiden jälkeen White vaipui pitkään pettymykseen. Hän ei löytänyt tuloksistaan minkäänlaista toivoa. Siitä huolimatta White jatkoi viimeistä harjoitteluaan ennen NOI-kilpailua. Säännöllisen harjoittelun ohella hän alkoi myös tutkia aiheita, joita hänellä ei ollut koskaan ollut tilaisuutta oppia OI-vuosiensa aikana — toivoen, että ennen jäähyväisiä mikään ei jäisi kaduttamaan.

Ravistaen harhailevat ajatukset mielestään White keskittyi yhtäkkiä edessään olevaan tehtävään, koruttomaan ja tylsään tietorakennetehtävään —

Whitella on $n$ kokonaisluvun jono $a_1, a_2, \dots, a_n$. Hän suorittaa tälle jonolle $q$ operaatiota. Jokainen operaatio on yksi seuraavista kolmesta tyypistä:

• 1 l r v — Lisää $v$ jokaiseen välin $[l, r]$ alkioon.
• 2 l r v — Aseta jokaisen välin $[l, r]$ alkion arvoksi $v$.
• 3 l r — Kysy lausekkeen $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ arvo modulo $2^{64}$.

Tehtäväsi on simuloida kaikki operaatiot ja tulostaa kaikkien kyselyiden tulokset.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n, q$ ($1 \le n, q \le 2 \times 10^5$), jotka kuvaavat alkioiden lukumäärää ja operaatioiden lukumäärää.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), jotka kuvaavat alkuperäisiä alkioita.

Jokainen seuraavista $q$ rivistä kuvaa yhden operaation yhdessä kolmesta muodosta:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), joka kuvaa lisäysoperaatiota.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), joka kuvaa asetusoperaatiota.
• 3 l r ($1 \le l \le r \le n$), joka kuvaa kyselyoperaatiota.

On taattu, että koko prosessin ajan jokaiselle $1 \le i \le n$ pätee $0 \le a_i \le 10^9$.

Tuloste

Tulosta jokaiselle kyselyoperaatiolle omalle rivilleen kokonaisluku — kyselyn tulos modulo $2^{64}$.

Esimerkit

Syöte

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

Tuloste

35
39
40
34
177
120

Syöte

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

Tuloste

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

Huomautus

Ensimmäisessä testitapauksessa:

Alkuperäinen jono on 2 3 5 4 1. Kolmannen operaation jälkeen siitä tulee 2 3 2 2 1, ja kuudennen operaation jälkeen siitä tulee 7 8 7 7 6.

Ensimmäisen kyselyn vastaus on $\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$.

Toisen kyselyn vastaus on $\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$.