F. Сумма на прогрессии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ из $$$n$$$ чисел. Также есть $$$q$$$ запросов вида $$$s, d, k$$$.

Для каждого из $$$q$$$ запросов найдите сумму элементов $$$a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k$$$. Иными словами, для каждого запроса нужно найти сумму $$$k$$$ элементов массива с индексами начиная с $$$s$$$-го, делая шаги, равные $$$d$$$, умножая на порядковый номер элемента в полученной последовательности.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка каждого набора содержит два числа $$$n, q$$$ ($$$1 \le n \le 10^5, 1 \le q \le 2 \cdot 10^5$$$) — количество чисел в массиве $$$a$$$ и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, ... a_n$$$ ($$$-10^8 \le a_1, ..., a_n \le 10^8$$$) — элементы массива $$$a$$$.

Следующие $$$q$$$ строк содержат по три целых числа $$$s$$$, $$$d$$$ и $$$k$$$ ($$$1 \le s, d, k \le n$$$, $$$s + d\cdot (k - 1) \le n$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам не превосходит $$$10^5$$$, и что сумма значений $$$q$$$ по всем наборам не превосходит $$$2 \cdot 10^5 $$$.

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

Для каждого набора входных данных в отдельной строке выведите $$$q$$$ чисел — желаемые суммы, разделенные пробелом.

Пример
Входные данные
5
3 3
1 1 2
1 2 2
2 2 1
1 1 2
3 1
-100000000 -100000000 -100000000
1 1 3
5 3
1 2 3 4 5
1 2 3
2 3 2
1 1 5
3 1
100000000 100000000 100000000
1 1 3
7 7
34 87 5 42 -44 66 -32
2 2 2
4 3 1
1 3 2
6 2 1
5 2 2
2 5 2
6 1 2
Выходные данные
5 1 3 
-600000000 
22 12 55 
600000000 
171 42 118 66 -108 23 2