eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Подсчет тюков сена

Подсчет тюков сена

Ферма Джона состоит из n полей в ряд последовательно пронумерованных 1..n. На каждом поле может быть произвольное количество стогов сена. Инструкции ФД бывают трёх видов:

1) Добавить один стог к каждому полю в указанном интервале

2) Определить минимальное количество стогов сена внутри указанного непрерывного интервала полей.

3) Посчитать суммарное количество стогов сена внутри указанного непрерывного интервала.

Входные данные

Первая строка содержит два положительных целых числа n (1n2 * 105) и q (1q105).

Следующая строка содержит n неотрицательных целых чисел, каждое не более, чем 105, указывающих, сколько стогов сена было изначально на каждом поле.

Каждая из следующих q строк содержит одну большую латинскую букву m, p или s, за которой следуют два положительных целых числа a и b (1abn), или три положительных целых числа a, b и c (1abn, 1c105). 3 числа будет только в том случае, если первая буква P.

Если первая буква M выведите минимальное количество стогов сена в интервале полей a..b.

Если первая буква P, добавьте по c стогов сена в каждое поле в интервале a..b.

Если первая буква S, выведите суммарное количество стогов сена в интервале полей a..b.

Выходные данные

Строка в выводе должна появится в ответ на каждый запрос вида M или S.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 5
3 1 2 4
M 3 4
S 1 3
P 2 3 1
M 3 4
S 1 3
Вихідні дані #1
2
6
3
8
Джерело 2015 USACO Декабрь, Платина