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.

给你一个包含 $n$ 个数字的数组 $a$。此外还有 $q$ 个形如 $s, d, k$ 的查询。

对于每个查询 $q$，求和式 $a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k$ 的值。换言之，对每个查询，需从第 $s$ 个元素开始，以步长 $d$ 取出数组中的 $k$ 个元素，并将每个元素乘以其在所取序列中的序号（从 $1$ 开始编号），最后求和。

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

每个测试包含若干测试用例。第一行包含一个整数 $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, \dots, a_n$（$-10^8 \le a_1, \dots, 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$。

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

对于每个测试用例，在单独一行中输出 $q$ 个数字——即所求的和，各数字之间用空格分隔。