e-olymp
Соревнования

Segment Tree - Multiple Update

Ужасные запросы

Мир становится все более злым и поэтому становится все сложнее попасть в Лигу Зла. Поскольку легендарная Плохая Лошадь ушла в отставку, теперь Вам следует правильно ответить на злые вопросы Доктора Ужасного, который имеет докторскую степень в ужасности (это не область компьютерных наук). У вас имеется массив из n элементов, изначально равных 0. Далее Вам заданы c следующих команд:

  • 0 p q v - следует прибавить значение v ко всем элементам массива с индексами от p до q включительно.

  • 1 p q - вывести строку, содержащую единственное число - сумму всех элементов массива между p и q включительно.

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

Первая строка содержит количество тестов. Каждый тест начинается со значений n (n100 000) и c (c100 000). Далее следуют c команд в выше описанном формате. Известно, что 1p, qn и 1v107.

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

Вывести ответы на запросы.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
Выходные данные #1
80
508