A16371. Sum of Progression

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.

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 $ .

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