Iván azt szeretné, ha komoly programozó válna belőle. Hogy ezt a célját elérje, úgy döntött, hogy utánozni fogja a személyeket akik a programozás verseny feladatokban megjelennek. Éppen ezért a szüleitől \(N\) természetes számból álló sorozatot kért, és mivel jó magaviseletű, szorgalmas tanuló, a szüleitől kapott is egy ilyen A_1, A_2, …, A_N elemekből álló sorozatot.

A sorozat mellé kapott is egy csomag kártyát is. A csomagban kétféle lapok találhatók:

• Az első típusú kártyán négy szám van: \(1\) \(l\) \(r\) \(x\). Amikor ezt a kártyalapot felhasználja a sorozat elemei melyek indexe \(l\) -től \(r\) - ig terjed, megváltoznak \(x\) értékkel (ha \(x\) pozitív, értékük megnő, ha negatív, akkor értékük csökken), vagyis \(A_l\) elem, \(A_l + x\) lesz, \(А_{l+1}\) elem \(A_{l+1} + x\) egészen \(A_r\)- ig amely értéke \(A_r + x\) lesz.
• A második kártyatípuson, csak egy \(2\) szám áll. Amikor ezt a kártyalapot használja fel, Iván feljegyzi a teljes sorozat elemeinek pillanatnyi összegét a papírra.

Minden kártyalapon ismertek a számok. Iván úgy játszik, hogy minden kártyalapot felhasznál pontosan egyszer, tetszőleges sorrendben. Azt szeretné elérni, hogy a felírt számok összege (amelyeket második típusú kártyalap felhasználásakor írt fel a papírra) a lehető legnagyobb legyen. Tekintettel arra, hogy ő még gyakorló versenyző, titeket, tapasztalt versenyzőket kért meg arra, hogy segítsetek neki ebben.

Bemenet

A bemenet első sorában az \(N\) szám, a sorozat hossza áll. A második sorban az \(N\) természetes szám: \(A_1, A_2, ... ,A_N\) - számok állnak, az \(A\) sorozat elemeinek kezdőértékei.

A harmadik sorban a \(Q\) egész szám áll, a kártyalapok száma a csomagban.

A következő \(Q\) sorban egy - egy kártyalap leírása található. Ha a sor \(1\) számmal kezdődik, első típusú kártyalapról van szó, és a sorban az \(l\), \(r\) és \(x\) számok következnek, ebben a sorrendben; ha a sor \(2\) számmal kezdődik, második típusú kártyalapról van szó.

Kimenet

A kimeneten kiíratni a feljegyzett számok lehető legnagyobb összegét.

Korlátozások

• \(1 \leq N,Q \leq 2\cdot10^5\)
• \(1 \leq A_i \leq 1000\)
• Az első típusú kártyalapokra vonatkozik, hogy \(1 \leq l \leq r \leq N\) és \(-1000 \leq x \leq 1000\).
• Legalább egy második típusú kártyalap létezik.
• Valamelyik első típusú kártyalap felhasználása után a sorozat elemei negatív értéket, vagy \(1000\) -nél nagyobb értéket is felvehetnek.

A tesztpéldák 4 független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek: az első típusú kártyalapra érvényes, hogy \(x \geq 1\).

• Tesztpéldák, melyek \(10\) pontot érnek: \(N, Q\leq 9\).

• Tesztpéldák, melyek \(30\) pontot érnek: \(N, Q \leq 5000\).

• Tesztpéldák, melyek \(50\) pontot érnek: nincs külön korlátozás.

Példák

1. példa

Bemenet

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

Kimenet

19

Magyarázat

Először az \(1\) \(2\) \(4\) \(2\) jelzésű kártyalapot használjuk fel, és akkor a sorozat \(3\) \(4\) \(3\) \(5\) \(1\) lesz. Ez után az \(1\) \(1\) \(3\) \(1\) jelzésű kártyalapot használjuk fel, és a sorozat \(4\) \(5\) \(4\) \(5\) \(1\) lesz. Végül a \(2\) jelzésű kártyalapot használjuk fel és a papírra \(4+5+4+5+1=19\) kerül.

2. példa

Bemenet

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

Kimenet

744

Megjegyzés

• A nagy számok miatt használjatok 64 bites egész számtípusokat (a C++ programnyelvben ez a long long típus).