Максимальная сумма подотрезка

Вам дан массив из n целых чисел и q запросов. Существует два типа запросов: обновить массив в позиции p и вычислить максимальную сумму подотрезка в диапазоне [l; r].

Под максимальной суммой подотрезка в [l; r] подразумевается сумма элементов такого непрерывного подотрезка [l'; r'], при которой сумма элементов оказывается наибольшей из всех возможных непустых подотрезков в пределах [l; r].

Входные данные

В первой строке заданы два числа n и q (1 ≤ n, q ≤ 100 000).

Во второй строке содержится n целых чисел: (от -10^9 до 10^9).

В следующих q строках располагаются запросы одного из двух видов: 1 l r (1 ≤ l ≤ r ≤ n) или 2 p x (1 ≤ p ≤ n, от -10^9 до 10^9). Они означают:

1. Найти максимальную сумму подотрезка в диапазоне [l; r].

2. Обновить значение массива в позиции p на x.

Выходные данные

Для каждого запроса первого типа выведите результат — то есть максимально возможную сумму подотрезка в заданном диапазоне.

Примеры