Sum of Progression
Contest: Codeforces Round 920 (Div. 3)
Difficulty rating: 1900
Tags: brute force, data structures, dp, implementation, math

You are given an array $$$a$$$ of $$$n$$$ numbers. There are also $$$q$$$ queries of the form $$$s, d, k$$$.

For each query $$$q$$$, find the sum of elements $$$a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k$$$. In other words, for each query, it is necessary to find the sum of $$$k$$$ elements of the array with indices starting from the $$$s$$$-th, taking steps of size $$$d$$$, multiplying it by the serial number of the element in the resulting sequence.

Input format:
Each test consists of several testcases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases. Next lines contain descriptions of testcases.

The first line of each testcase contains two numbers $$$n, q$$$ ($$$1 \le n \le 10^5, 1 \le q \le 2 \cdot 10^5$$$) — the number of elements in the array $$$a$$$ and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, ... a_n$$$ ($$$-10^8 \le a_1, ..., a_n \le 10^8$$$) — elements of the array $$$a$$$.

The next $$$q$$$ lines each contain three integers $$$s$$$, $$$d$$$, and $$$k$$$ ($$$1 \le s, d, k \le n$$$, $$$s + d\cdot (k - 1) \le n$$$ ).

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5$$$, and that the sum of $$$q$$$ over all testcases does not exceed $$$2 \cdot 10^5 $$$.

Output format:
For each testcase, print $$$q$$$ numbers in a separate line — the desired sums, separated with space.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Example input:
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

Example output:
5 1 3 
-600000000 
22 12 55 
600000000 
171 42 118 66 -108 23 2

Editorial:
The key idea is that we know how to calculate the sum $$$(i - l + 1) \cdot a_i$$$ for $$$l \le i \le r$$$ fast – we need to calculate all prefix sums $$$i \cdot a_i$$$ and $$$a_i$$$ for $$$1 \le i \le k$$$, then take the difference between the $$$r$$$-th and $$$(l-1)$$$-th of $$$i \cdot a_i$$$ and subtract the difference between the $$$r$$$-th and $$$(l-1)$$$-th multiplied by $$$l - 1$$$. This way queries with step $$$1$$$ will be processed in $$$O(n + q)$$$ time, where $$$q$$$ is the total amount of queries with step 1.
But this idea can be generalized to the following: we can precalculate all the prefix sums and all the prefix sums with multiplication by index for every $$$d_0 \le d$$$ in $$$O(n \cdot d)$$$ time, and then process all queries with step $$$d_0 \le d$$$ in $$$O(1)$$$ time.
However, for all other queries we can process a single query in $$$O(n / d)$$$ time, because the difference between consecutive elements in the resulting sequence is greater than $$$d$$$.
Combining these two ideas, we get a solution with a time complexity $$$O(n \cdot d + q \cdot n / d)$$$. Setting $$$d = \sqrt{q}$$$, we get a solution with a time complexity $$$O(n \sqrt{q})$$$. The model solution fixes the value of $$$d = 322$$$, which is equal to $$$\sqrt{MAX}$$$.
Interestingly, this solution can be generalized to calculate the sums $$$(i + 1) ^ 2 \cdot a_{s + d \cdot i}$$$.