eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Жахливі запити

Жахливі запити

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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