Sottoarray a somma massima

Ti viene fornito un array di n interi e q interrogazioni. Esistono due tipi di interrogazioni: aggiornare l’array in una posizione specifica p, oppure calcolare il sottoarray a somma massima all’interno di un sottoarray [l; r].

Il sottoarray a somma massima all’interno di [l; r] è definito come il sottoarray contiguo che ha la somma più alta dei propri elementi. In altre parole, devi trovare la somma del sottoarray [l'; r'] tale che la somma dei suoi elementi sia la più grande possibile tra tutti i sottoarray non vuoti compresi nell’intervallo [l; r].

Input

La prima riga dell’input contiene due interi n e q (1 ≤ n, q ≤ 100 000).

La riga successiva contiene n interi separati da spazio ( ≤ ≤ ).

Le successive q righe contengono tutte le interrogazioni: 1 l r (1 ≤ l ≤ r ≤ n) o 2 p x (1 ≤ p ≤ n, ≤ x ≤ ), che rappresentano i due tipi di operazioni:

1. Ottenere il sottoarray a somma massima in [l; r].

2. Aggiornare l’array in posizione p con il valore x.

Output

Per ogni interrogazione di tipo 1, il programma deve stampare la risposta corrispondente.

Esempi