1. Totálny intervaláč

Nina (nie tá Nina, iná Nina) sa veľmi zaujíma o programovanie. Zistila, že v jednej dobrej škole existuje jeden dobrý programátorský krúžok, ktorý vedie jeden preslávený Samko Gurský, a.k.a. Hodobox. Celý týždeň chúlostivo túžila a nevedela sa dočkať, kedy už konečne nadíde pondelok a bude môcť prísť.

Nadišiel pondelok a Nine sa začal vytúžený deň. Skončila školu, kúpila si kebab, nastúpila do autobusu, vystúpila, prešla cez prechod, hore po schodoch a sadla si do lavice spolu s ostatnými. Nastražila uši a počúvala. Samko rozprával.

“Intervalové stromy sú taká pekná dátová štruktúra, s ktorou vieme rýchlo vykonávať všeliaké operácie na súvislých úsekoch postupnosti prvkov…”

Samko vysvetlil, ako robiť súčtový intervaláč a okrajom spomenul, že intervaláč sa dá spraviť pre takmer hocijakú matematickú operáciu. Vtedy Nine vhupla do hlavy veľká myšlienka: Čo tak spraviť intervaláč, ktorý bude robiť všetko? Sčítavať, odčítavať, násobiť, deliť, zisťovať súčet, minimum, maximum, priemer, všetko!

S týmto magnificentným nápadom sa zdôverila Hodoboxovi, ktorý ju však vysmial a odporučil, aby začala s nejakým menším nápadom. Nina si jeho radu zobrala k srdcu a zredukovala svoj intervaláč na sčítavanie, delenie, zisťovanie súčtu a minima. S týmto novým nápadom už nešla za Hodoboxom. Bála sa, že ju opäť vysmeje. Šla radšej za Mišom. Ten bol z jej nápadu nadšený a rozhodol sa, že ho použije ako úlohu do KSP.

Úloha

Máme pole \(n\) čísel (\(n \leq 10^5\)) v rozsahu od \(-10^9\) po \(10^9\) vrátane. Prichádza nám \(q\) požiadaviek (\(q \leq 10^5\)), pre všetky požiadavky platí \(0 \leq l \leq r \leq n - 1\) a každá má jeden z nasledovných tvarov:

• 1 l r c : Ku každému číslu v poli s indexom v intervale \(l \dots r\) (vrátane) pripočítame číslo \(c\) (\(-10^4 \leq c \leq 10^4\)).
• 2 l r d : Každé číslo v poli s indexom v intervale \(l \dots r\) (vrátane) celočíselne vydeľ číslom \(d\) (\(2 \leq d \leq 10^9\)), so zaokrúhlením smerom nadol.
• 3 l r : Nájdi a vypíš najmenšie z čísel v poli s indexami v intervale \(l \dots r\) (vrátane).
• 4 l r : Nájdi a vypíš súčet všetkých čísel v poli s indexami v intervale \(l \dots r\) (vrátane).

Formát vstupu

Prvý riadok obsahuje dve čísla: \(n\) a \(q\) oddelené medzerou.

Druhý riadok obsahuje \(n\) čísel oddelených medzerou: počiatočné hodnoty čísel v poli.

Nasledujúcich \(q\) riadkov obsahuje popisy jednotlivých požiadaviek vo formáte, ako je popísané vyššie.

Sú štyri testovacie sady, v prvej zo sád navyše platí \(n \leq 10\,000\) a \(q \leq 5\,000\).

Formát výstupu

Pre každú požiadavku typu 3 a 4 treba vypísať jeden riadok obsahujúci jedno číslo: odpoveď na danú požiadavku.

Príklad

Input:

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

Output:

-2
-2
-2
-2
0
1
1