ЗАДАЧА Сугробы на ЛЭП

Служба электроснабжения проводит мониторинг уровня снега, лежащего на ЛЭП Нью-Васюки - Москва. Вся ЛЭП разбивается на участки опорами. Снег имеет свойства падать на какой-либо интервал ЛЭП, если там уже лежал какой-либо снег, то высота снежного покрова на этом участке суммируется. Также снег имеет тенденцию таять на участке трассы в результате оттепели, при этом известно, что не бывает сугробов отрицательной высоты. Энергетикам крайне важно уметь узнавать суммарную высоту снежного покрова на некоторых последовательных участках, чтобы знать вероятность обрыва проводов.

ВХОДНЫЕ ДАННЫЕ

В первой строке входного файла содержатся два числа: 𝑁 — (1≤𝑁≤10000) и 𝑀 – количество команд (1≤𝑀≤50000) . Каждая команда имеет вид 1 𝐿 𝑅 𝑆 , что означает, что на участок с 𝐿 -ой опоры по 𝑅 -ую опору выпало 𝑆 сантиметров снега (𝑆 может быть и отрицательным, тогда это означает, что такое количества снега растаяло), или 2 𝐿 𝑅 — запрос суммарной высоты снега на участке с 𝐿 -ой опоры по 𝑅 -ую. Опоры нумеруются от 0 до 𝑁 . Гарантируется, что для запросов вида 1 𝐿 𝑅 𝑆 при 𝑆<0 на каждом участке между опорами 𝐿 и 𝑅 уровень снега составляет не менее 𝑆 .

ВЫХОДНЫЕ ДАННЫЕ

На каждую команду 2 (запрос) вы должны выводить число 𝐾 – суммарную высоту снежного покрова, лежащего на проводах с 𝐿 -ой опоры по 𝑅 -ую. Каждое число должно выводиться на новой строке. Известно, что в процессе работы суммарное количество снега на любом интервале не превышает 2^31

ПРИМЕРЫ

Автор задачи: FunRoom