Задача D. Накопительная система ≡

Условие

У Пети есть N копилок. Изначально все копилки пусты. Мальчик может совершать два действия:

• 1 i m d — положить во все копилки следующее количество монет: max(0, m − d ⋅ |i − j|), где j — номер копилки, куда кладутся моменты. Проще говоря, в копилку i кладётся m монет, в копилки i − 1 и i + 1 — m − d монет, i + 2 и i − 2 — m − 2 ⋅ d и т.д. до нуля.
• 2 l r — узнать суммарное количество монет в копилках с номерами от l до r.

Сегодня Петя задумал выполнить Q действий. Помогите ему узнать ответ для каждого действия второго типа.

Формат входных данных

Первая строка содержит два целых числа N и Q — количество копилок и количество действий, которые Петя собирается совершить.

Далее следует Q строк, в каждой из которых записано одно действие в формате, описанном в условии задачи.

Формат выходных данных

Для каждого действия второго типа выведите строку, содержащую одно целое число.

Ограничения

1 ≤ N, Q ≤ 10⁵

1 ≤ d ≤ m ≤ 10⁵

1 ≤ i, l, r ≤ N

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

8 10
2 1 8
1 1 3 1
2 1 2
1 3 7 2
2 2 5
2 1 8
1 7 10 8
2 1 8
2 3 3
2 4 7

0
5
23
30
44
8
21