Млади Иван је одлучио да постане озбиљан такмичар из програмирања и његов план да то оствари се састоји из тога да имитира ликове из текстова задатака са такмичења. Баш због тога је за рођендан од родитеља тражио низ природних бројева дужине \(N\), а пошто је добар дечак и вредан ученик, добио је баш такав низ, низ \(A_1, A_2, ..., A_N\).

Уз низ је добио и шпил од \(Q\) картица. Постоје два типа картица:

• На првом типу картице налазе се четири броја: \(1\) \(l\) \(r\) \(x\). Када се картица овог типа искористи елементи низа са индексима од \(l\) do \(r\) се промене за \(x\) (ако је \(x\) позитивно онда се повећају, ако је негативно онда се смање), тј. елемент \(A_l\) постаје \(A_l + x\), елемент \(А_{l+1}\) постаје \(A_{l+1} + x\) и тако до \(A_r\) који постаје \(A_r + x\).
• На другом типу картице налази се само број \(2\). Када се картица овог типа искористи, Иван записује тренутни збир свих елемената низа на папир

За сваку картицу, ви знате бројеве који су записани на њој. Иван се игра тако да искористи сваку картицу тачно једном, али може их искористити у било ком редоследу. Његова жеља је да укупан збир свих бројева који су записани на папир (услед коришћења картице другог типа) буде што је већи могућ. Пошто је још увек такмичар у тренингу, замолио је вас, искусне такмичаре, да му помогнете да то уради.

Опис улаза

У првом реду улаза се налази природан број \(N\) – дужина низа. У другом реду се налази низ \(N\) природних бројева \(A_1, A_2, ... ,A_N\) – почетне вредности низа \(A\). У трећем реду се налази природан број \(Q\) – број картица. У наредних \(Q\) линија налазе се описи картица: уколико ред почиње са \(1\), у питању је картица првог типа и у истом реду следе природни бројеви \(l\), \(r\) i \(x\) тим редом; уколико ред почиње са \(2\), у питању је картица другог типа.

Опис излаза

На излаз исписати највећи могући збир записаних бројева.

Ограничења

• \(1 \leq N,Q \leq 2\cdot10^5\)
• \(1 \leq A_i \leq 1000\)
• За картице првог типа важиће \(1 \leq l \leq r \leq N\) и \(-1000 \leq x \leq 1000\).
• Постојаће бар једна картица другог типа.
• Могуће је да након коришћења неких картица првог типа елементи низа буду негативни или већи од \(1000\).

Тест примери су подељени у 4 дисјунктне групе:

• У тест примерима вредним \(10\) поена: За картице првог типа важиће \(x \geq 1\).
• У тест примерима вредним \(10\) поена: \(N, Q\leq 9\).
• У тест примерима вредним \(30\) поена: \(N, Q \leq 5000\).
• У тест примерима вредним \(50\) поена: Без додатних ограничења.

Примери

Пример 1

Улаз

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

Излаз

19

Објашњење

Искористимо прво картицу \(1\) \(2\) \(4\) \(2\), тада низ постаје \(3\) \(4\) \(3\) \(5\) \(1\). Након тога искористимо картицу \(1\) \(1\) \(3\) \(1\), тада низ постаје \(4\) \(5\) \(4\) \(5\) \(1\). На крају искористимо картицу \(2\), и на папир записујемо збир \(4+5+4+5+1=19\).

Пример 2

Улаз

7
33 11 73 78 12 62 84
5
1 2 5 3
2
1 2 6 -5
2
1 1 7 1

Излаз

744

Напомена

• Због величине бројева, користите 64-битне типове целих бројева (нпр. у C++ тип long long).