给你一个由 $$$n$$$ 数字组成的数组 $$$a$$$。还有 $$$q$$$ 形式的 $$$s、d、k$$$ 查询。
对于每个查询 $$$q$$$,求元素 $$$a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k$$$ 的总和。换句话说,对于每个查询,需要找到数组中 $$$k$$$ 元素的总和,索引从 $$$s$$$ 开始,步长为 $$$d$$$,将其乘以结果序列中元素的序列号。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$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, ... a_n$$$ ($$$-10^8 \le a_1, ..., 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 $$$。
输出
对于每个测试用例,在单独的行中打印 $$$q$$$ 数字 - 所需的总和,用空格分隔。
示例
输入 #1
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
输出 #1
5 1 3 -600000000 22 12 55 600000000 171 42 118 66 -108 23 2