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