409680: GYM103678 C Бернард и запросы на арифметических прогрессиях

C. Бернард и запросы на арифметических прогрессияхограничение по времени на тест7 секундограничение по памяти на тест1024 мегабайтавводстандартный вводвыводстандартный вывод

Рудольф подарил Бернарду на День рождения массив из $$$N$$$ чисел: $$$A_1, A_2, ..., A_N$$$. Бернарду очень нравятся арифметические прогрессии, поэтому он придумал $$$Q$$$ запросов на арифметических прогрессиях. Запросы могут быть двух типов:

• $$$1$$$ $$$i$$$ $$$d$$$ $$$k$$$ $$$v$$$ — прибавить к числам $$$A_i, A_{i + d}, A_{i + 2\cdot d}, ..., A_{i + (k - 1) \cdot d}$$$ число $$$v$$$.
• $$$2$$$ $$$i$$$ $$$d$$$ $$$k$$$ — найти значение выражения $$$A_i + A_{i + d} + A_{i + 2\cdot d}\,+\,...\,+\,A_{i + (k - 1) \cdot d}$$$.

Помогите Бернарду и выведите ответ на каждый запрос второго типа.

Входные данные

Первая строка входных данных содержит два целых числа $$$N$$$ и $$$Q$$$ ($$$1 \le N, Q \le 2\cdot10^5$$$).

Вторая строка содержит $$$N$$$ целых чисел $$$A_1, A_2, ..., A_n$$$ ($$$-10^5 \le A_i \le 10^5$$$).

Затем следуют $$$Q$$$ строк, каждая задает запрос:

• $$$1$$$ $$$i$$$ $$$d$$$ $$$k$$$ $$$v$$$ ($$$i > 0, k > 0, i + (k-1) \cdot d \le n, -10^5 \le v \le 10^5$$$)
• $$$2$$$ $$$i$$$ $$$d$$$ $$$k$$$ ($$$i > 0, k > 0, i + (k-1) \cdot d \le n$$$)

Выходные данные

Выведите ответ на каждый запрос второго типа.

Система оценки

Группа	Доп. ограничения	Баллы	Требуемые подзадачи	Тип проверки
$$$1$$$	$$$N, Q \le 1000$$$	$$$10$$$	—	Полная
$$$2$$$	$$$d = 1$$$ для всех запросов	$$$16$$$	—	Полная
$$$3$$$	$$$t_j \le t_{j + 1} (0 \le j \le q - 1) $$$	$$$20$$$	—	Полная
	где $$$t_j$$$ - тип $$$j$$$-го запроса ($$$1$$$ или $$$2$$$)
$$$4$$$	$$$d = 1$$$ для запросов 2-го типа	$$$24$$$	$$$2$$$	Полная
$$$5$$$	—	$$$30$$$	$$$1-4$$$	Полная

ПримерВходные данные

5 5
3 0 -2 1 -6
2 1 3 2
1 2 2 2 4
2 1 3 2
1 3 1 3 -3
2 1 2 3

Выходные данные

4
8
-11