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

Світ стає все більш злим і тому стає все складніше потрапити до Ліги Зла. Оскільки легендарний Поганий Кінь пішов у відставку, тепер Вам слід правильно відповісти на злі питання Доктора Жахливого, який має докторську ступінь в жахливості (це не область комп'ютерних наук). У вас є масив з $n$ елементів, спочатку рівних $0$. Далі Вам задані $c$ наступних команд:

• $0pqv$ — слід додати значення $v$ до усіх елементів масиву з індексами від $p$ до $q$ включно.

• $1pq$ — вивести рядок, що містить єдине число — суму усіх елементів масиву між $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$.

Вихідні дані

Вивести відповіді на запити.

Приклади