311017: CF1921F. Sum of Progression

F. Sum of Progressiontime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

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

Output

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

题目大意：给定一个数组和一个查询序列，每个查询包括三个参数 s, d, k。对于每个查询，计算数组中从第 s 个元素开始，每隔 d 个元素取一个，共取 k 个元素，按照取出的顺序分别乘以 1, 2, ..., k，然后求和。

输入数据格式：
- 第一行包含一个整数 t，表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 n 和 q，分别表示数组 a 的长度和查询的数量。
- 每个测试用例的第二行包含 n 个整数，表示数组 a 的元素。
- 接下来 q 行，每行包含三个整数 s, d, k，表示一个查询。

输出数据格式：
- 对于每个测试用例，输出 q 个整数，每个整数对应一个查询的结果，每个结果之间用空格分隔。

LaTeX 格式的公式：
给定数组 $ a $ 的长度为 $ n $，查询序列中的每个查询为 $ (s, d, k) $，需要计算的是：
$$
a_s + a_{s+d} \times 2 + a_{s+d \times 2} \times 3 + \dots + a_{s+d \times (k-1)} \times k
$$题目大意：给定一个数组和一个查询序列，每个查询包括三个参数 s, d, k。对于每个查询，计算数组中从第 s 个元素开始，每隔 d 个元素取一个，共取 k 个元素，按照取出的顺序分别乘以 1, 2, ..., k，然后求和。 输入数据格式： - 第一行包含一个整数 t，表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 n 和 q，分别表示数组 a 的长度和查询的数量。 - 每个测试用例的第二行包含 n 个整数，表示数组 a 的元素。 - 接下来 q 行，每行包含三个整数 s, d, k，表示一个查询。 输出数据格式： - 对于每个测试用例，输出 q 个整数，每个整数对应一个查询的结果，每个结果之间用空格分隔。 LaTeX 格式的公式： 给定数组 $ a $ 的长度为 $ n $，查询序列中的每个查询为 $ (s, d, k) $，需要计算的是： $$ a_s + a_{s+d} \times 2 + a_{s+d \times 2} \times 3 + \dots + a_{s+d \times (k-1)} \times k $$