Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

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

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

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

Опис улаза

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

Опис излаза

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

Ограничења

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

Примери

Пример 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

Напомена