ТШ 2022

Задача E3. RMQ ≡

Входной файл:	rmq.in		Ограничение времени:	2 сек
Выходной файл:	rmq.out		Ограничение памяти:	256 Мб

Дан массив a[1..n]. Требуется написать программу, обрабатывающую два типа запросов.

«max l r». Найти максимум в массиве a от l-ой ячейки до r-ой включительно.
«add l r v». Прибавить значение v к каждой ячейке a[] от l-ой до r-ой включительно.

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 10⁵) — длина массива и число запросов соответственно.

Вторая строка содержит n целых чисел a₁, …, a_n (|a_i| ≤ 10⁵), задающих соответствующие значения массива.

Следующие q строк содержат запросы.

В зависимости от типа запрос может иметь вид либо «max l r», либо «add l r v».

1 ≤ l ≤ r ≤ n, |v| ≤ 10⁵.

Для каждого запроса вида «max l r» требуется в отдельной строке выдать значение соответствующего максимума.

№	Входной файл (`rmq.in`)	Выходной файл (`rmq.out`)
1	`5 3 1 2 3 4 -5 max 1 3 add 1 2 5 max 1 3`	`3 7`