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

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

Входные данные #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 Декабрь, Платина