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 \gt 0, k \gt 0, i + (k-1) \cdot d \le n, -10^5 \le v \le 10^5$$$)
  • $$$2$$$ $$$i$$$ $$$d$$$ $$$k$$$ ($$$i \gt 0, k \gt 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