Жахливі запити
Жахливі запити
Світ стає все більш злим і тому стає все складніше потрапити до Ліги Зла. Оскільки легендарний Поганий Кінь пішов у відставку, тепер Вам слід правильно відповісти на злі питання Доктора Жахливого, який має докторську ступінь в жахливості (це не область комп'ютерних наук). У вас є масив з 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