Maximale Teilarraysumme

Sie haben ein Array aus n Ganzzahlen und q Abfragen (Queries). Es gibt zwei Arten von Abfragen: Entweder wird das Array an einem bestimmten Index p aktualisiert, oder es wird die maximale Teilarraysumme in einem Abschnitt [l; r] berechnet.

Das sogenannte Maximum Sum Subarray innerhalb eines Abschnitts [l; r] ist das zusammenhängende Teilarray, dessen Summe aller Elemente maximal ist. Anders ausgedrückt, Sie suchen die Summe eines Teilarrays [l'; r'], welches unter allen möglichen nicht-leeren Teilarrays im Bereich [l; r] die größte Summe aufweist.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen n und q (1 ≤ n, q ≤ 100 000).

Die nächste Zeile enthält n durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ).

Die folgenden q Zeilen enthalten sämtliche Abfragen in der Form 1 l r (1 ≤ l ≤ r ≤ n) oder 2 p x (1 ≤ p ≤ n, ≤ x ≤ ). Diese beiden Arten von Abfragen haben folgende Bedeutung:

1. Bestimme die maximale Teilarraysumme im Abschnitt [l; r].

2. Aktualisiere den Wert im Array an Position p mit dem Wert x.

Ausgabe

Für jede Abfrage vom Typ 1 soll das Programm die entsprechende Antwort ausgeben.

Beispiele