Ужасные запросы
Ужасные запросы
Мир становится все более злым и поэтому становится все сложнее попасть в Лигу Зла. Поскольку легендарная Плохая Лошадь ушла в отставку, теперь Вам следует правильно ответить на злые вопросы Доктора Ужасного, который имеет докторскую степень в ужасности (это не область компьютерных наук). У вас имеется массив из n элементов, изначально равных 0. Далее Вам заданы c следующих команд:
0~p~q~v — следует прибавить значение v ко всем элементам массива с индексами от p до q включительно.
1~p~q — вывести строку, содержащую единственное число — сумму всех элементов массива между p и q включительно.
Входные данные
Первая строка содержит количество тестов. Каждый тест начинается со значений n~(n \le 10^5) и c~(c \le 10^5). Далее следуют c команд в выше описанном формате. Известно, что 1 \le p, q \le n и 1 \le v \le 10^7.
Выходные данные
Вывести ответы на запросы.
Пример
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
80 508