Подсчет тюков сена
Подсчет тюков сена
Ферма Джона состоит из n полей в ряд последовательно пронумерованных 1..n. На каждом поле может быть произвольное количество стогов сена. Инструкции ФД бывают трёх видов:
Добавить один стог к каждому полю в указанном интервале
Определить минимальное количество стогов сена внутри указанного непрерывного интервала полей.
Посчитать суммарное количество стогов сена внутри указанного непрерывного интервала.
Входные данные
Первая строка содержит два положительных целых числа n (1 ≤ n ≤ 2 * 10^5
) и q (1 ≤ q ≤ 10^5
).
Следующая строка содержит n неотрицательных целых чисел, каждое не более, чем 10^5
, указывающих, сколько стогов сена было изначально на каждом поле.
Каждая из следующих q строк содержит одну большую латинскую букву M, P или S, за которой следуют два положительных целых числа a и b (1 ≤ a ≤ b ≤ n), или три положительных целых числа a, b и c (1 ≤ a ≤ b ≤ n, 1 ≤ c ≤ 10^5
). 3 числа будет только в том случае, если первая буква P.
Если первая буква M выведите минимальное количество стогов сена в интервале полей a..b.
Если первая буква P, добавьте по c стогов сена в каждое поле в интервале a..b.
Если первая буква S, выведите суммарное количество стогов сена в интервале полей a..b.
Выходные данные
Строка в выводе должна появится в ответ на каждый запрос вида M или S.
Пример
4 5 3 1 2 4 M 3 4 S 1 3 P 2 3 1 M 3 4 S 1 3
2 6 3 8