Запити красот підмасивів

Назвемо вагою масиву цілих чисел $b$ довжини $m$ модуль суми його елементів, тобто $|b_1+b_2+...+b_m|$.

Визначимо красу розбиття масиву $c$ на кілька підмасивів як мінімальну вагу серед ваг підмасивів. Формально, красою розбиття масиву $c$ на $k$ підмасивів $[c_1,\dots ,c_{p_1}],[c_{p_1+1},\dots ,c_{p_2}],\dots ,[c_{p_{k-1}+1},\dots ,c_{p_k}]$, де $1\le p_1<p_2<\dots <p_{k-1}<p_k=n$, є значення $\min (|c_1+\dots +c_{p_1}|,|c_{p_1+1}+\dots +c_{p_2}|,\dots ,|c_{p_{k-1}+1}+\dots +c_{p_k}|)$. Наприклад, розбиття масиву $[3,-6,4,5,-8]$ на підмасиви $[3,-6],[4],[5,-8]$ має красу $\min (|3+(-6)|,|4|,|5+(-8)|)=\min (3,4,3)=3$.

Визначимо красу масиву $c$ як максимальну красу серед усіх можливих його розбиттів на підмасиви.

Задано масив цілих чисел $a$ довжини $n$.

Необхідно виконати $q$ запитів. Запити бувають двох типів:

1. знайти красу масиву, що складається з елементів $[a_l,a_{l+1},\dots ,a_r]$, де ($l$, $r$) — параметри запиту;

2. замінити елемент $a_x$ на $v$, де ($x$, $v$) — параметри запиту.

Вхідні дані

У першому рядку задано два цілих числа $n$, $q$ ($1\le n,q\le 10^6$) — довжина масиву $a$ та кількість запитів відповідно.

У другому рядку задано $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($-10^9\le a_i\le 10^9)$ — елементи масиву $a$.

У наступних $q$ рядках задано по три цілі числа. Перше з чисел $typ{e}_i$ ($1\le typ{e}_i\le 2$) позначає тип запиту. Запити першого типу задані у форматі «1 l r» ($1\le l\le r\le n$), а запити другого типу задані у форматі «2 x v» ($1\le x\le n,$ $-10^9\le v\le 10^9$).

Вихідні дані

Для кожного запиту першого типу в окремому рядку виведіть одне ціле число — красу відповідного масиву.

Приклади

Примітка

У першому прикладі для третього запиту максимальна краса розбиття масиву $[-3,4,2,-5]$ досягається при розбитті на підмасиви $[-3],[4,2],[-5]$.

У другому прикладі для першого запиту максимальна краса розбиття масиву $[1,-2,3,-4]$ досягається при розбитті на підмасиви $[1,-2,3],[-4]$.

Оцінювання

1. ($4$ бали): $typ{e}_i=1$ для $1\le i\le q$; $a_i>0$ для $1\le i\le n$;

2. ($14$ балів): $typ{e}_i=1$ для $1\le i\le q$; $n,q\le 1000$;

3. ($10$ балів): $typ{e}_i=1$ для $1\le i\le q$; $n,q\le 2\cdot 10^5$, для кожного запиту існує оптимальне розбиття на не більше ніж $2$ підмасиви;

4. ($10$ балів): $typ{e}_i=1$ для $1\le i\le q$; $q\le n\le 2\cdot 10^5$, $l_i=1$, $r_i=i$ для $1\le i\le q$;

5. ($11$ балів): $typ{e}_i=1$ для $1\le i\le q$; $n,q\le 2\cdot 10^5$, $-5\le \sum _{j=1}^i{a}_j\le 5$ для $1\le i\le n$;

6. ($18$ балів): $typ{e}_i=1$ для $1\le i\le q$; $n,q\le 2\cdot 10^5$;

7. ($9$ балів): $typ{e}_i=1$ для $1\le i\le q$;

8. ($16$ балів): $n,q\le 2\cdot 10^5$;

9. ($8$ балів): без додаткових обмежень.