Subarreglo de Suma Máxima

Se te proporciona un arreglo de n enteros y q consultas. Existen dos tipos de consultas: actualizar el arreglo en un índice p y calcular el subarreglo de suma máxima dentro de un subarreglo [l; r].

El subarreglo de suma máxima dentro de [l; r] se define como el subarreglo contiguo que tenga la mayor suma de sus elementos. En otras palabras, se debe hallar la suma del subarreglo [l'; r'] cuyo total sea máximo entre todos los subarreglos no vacíos dentro del rango [l; r].

Entrada

La primera línea de la entrada contiene dos enteros n y q (1 ≤ n, q ≤ 100 000).

La siguiente línea contiene n enteros separados por espacio: ( ≤ ≤ ).

A continuación, se dan q líneas que representan todas las consultas, las cuales pueden ser de la forma 1 l r (1 ≤ l ≤ r ≤ n) o 2 p x (1 ≤ p ≤ n, ≤ ≤ ), indicando los dos tipos de consultas:

1. Obtener el subarreglo de suma máxima dentro del subarreglo [l; r].

2. Actualizar la posición p del arreglo con el valor x.

Salida

Para cada consulta de tipo 1, el programa debe imprimir la respuesta correspondiente a dicha consulta.

Ejemplos