Codeforces Round 920 (Div. 3) |
---|
Закончено |
Дан массив $$$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$$$ чисел — желаемые суммы, разделенные пробелом.
53 31 1 21 2 22 2 11 1 23 1-100000000 -100000000 -1000000001 1 35 31 2 3 4 51 2 32 3 21 1 53 1100000000 100000000 1000000001 1 37 734 87 5 42 -44 66 -322 2 24 3 11 3 26 2 15 2 22 5 26 1 2
5 1 3 -600000000 22 12 55 600000000 171 42 118 66 -108 23 2
Название |
---|