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