Задача D. RMQ

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

Условие

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

Формат входного файла

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

Вторая строка содержит n целых чисел a1, …, an (|ai| ≤ 105), задающих соответствующие значения массива.

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

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

1 ≤ l ≤ r ≤ n, |v| ≤ 105.

Формат выходного файла

Для каждого запроса вида «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

0.143s 0.018s 15