Маючи масив із \(n\) цілих чисел, ваше завдання — обробити \(q\) запитів наступних типів:

1. оновити значення в позиції \(k\) до \(u\)

2. яка максимальна сума префіксів у діапазоні [\(a,b\)]?

Формат вхідних даних

Перший рядок містить два цілих числа \(n\) і \(q\): кількість значень і запитів.

У другому рядку є \(n\) цілих чисел \(x_1,x_2,…,x_n\): значення масиву.

Нарешті, є \(q\) рядків, що описують запити.

У кожному рядку є три цілі числа: «1 k u» або «2 a b».

Обмеження

• \(1≤n,q≤2*10^5\)
• \(−10^9≤x_i,u≤10^9\)
• \(1≤k≤n\)
• \(1≤a≤b≤n\)

Формат вихідних даних

Виведіть результат кожного запиту типу 2.

Приклад вхідних даних

8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4

Приклад вихідних даних

5
2
0