Johnie a început să se joace cu un vector de numere. El dispune iniţial de un vector V cu N numere întregi (numerotate de la 0 la N - 1) şi poate efectua următoarele operaţii:

• schimbarea elementului de pe poziţia p cu un alt număr întreg;
• aflarea subsecvenţei de sumă maximă din V inclusă între indicii a şi b;

Cerința

Ajutaţil pe Johnie să efectueze repede operaţiile de mai sus.

Date de intrare

Fișierul maxq.in conţine pe prima linie numărul N reprezentând dimensiunea vectorului. Pe următoarea linie se găsesc N elemente reprezentând valorile iniţiale ale vectorului. Urmatoarea linie conţine M, reprezentând numărul de operaţii. Pe fiecare dintre următoarele M linii sunt descrise cele M operaţii în forma următoare:

• 0 i p: numărul 0 de la început codifică faptul că operaţia curentă este una de schimbare; astfel elementul de pe poziţia i a vectorului se înlocuieşte cu numarul întreg p;

• 1 a b: numărul 1 de la început codifică faptul că operaţia curentă este o întrebare; astfel se cere să se afle subsecvenţa de sumă maximă din vector inclusă între indicii a şi b (a ≤ b);

Date de ieșire

Fişierul maxq.out trebuie să conţină un număr de linii egal cu numărul de întrebări din fişierul de intrare. Pe linia i se cere să se afişeze un singur număr reprezentând suma maximă ce se poate obţine în contextul întrebării i din fişierul de intrare (i = 1, 2, ...); în cazul în care vor exista doar subsecvenţe de sumă negativă se va afişa 0.

Restricții și precizări

• 1 ≤ N ≤ 200.000;
• 1 ≤ M ≤ 200.000;
• toate elementele vectorului aparţin intervalului [-100.000, 100.000];
• definim o subsecvenţă ca fiind un şir de termeni consecutivi din vector, iar suma ei se obţine adunând elementele ce o compun;
• există cel puţin o întrebare.
• pentru 20% din teste se garantează N ≤ 5.000

Exemplu:

maxq.in

5
1 -10 4 -1 9
4
1 0 3
0 1 1
1 0 3
1 2 4
1 2 4

maxq.out

4 
6 
12 

Explicație

Pentru prima întrebare se alege subsecvenţa formată de elementul pe poziţia 2 din vector. Pentru a 2-a întrebare se aleg primele 3 elemente din vector (elementul de pe poziţia 1 a fost schimbat). Pentru a 3-a întrebare se aleg toate elementele din intervalul cerut.