等差数列之和

• 时间限制：2 秒
• 内存限制：1024 MiB

题目描述

给定一个长度为 $n$ 的整数数组 $a$。你需要回答 $q$ 个查询，每个查询由三个整数 $s,d,k$ 描述。

对于一次查询，求

也就是说，从下标 $s$ 开始，每次向后移动 $d$ 个位置，共取 $k$ 个元素，并依次乘以 $1,2,\ldots,k$ 后求和。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

每组测试数据的第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行包含三个整数 $s,d,k$，描述一次查询。

输出格式

对于每组测试数据，输出一行 $q$ 个整数，依次表示各次查询的答案，相邻整数之间用一个空格分隔。

样例输入

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

样例输出

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

数据范围

保证：

• $1\le t\le 10^4$；
• $1\le n\le 10^5$，$1\le q\le 2\times 10^5$；
• $-10^8\le a_i\le 10^8$；
• $1\le s,d,k\le n$；
• $s+d(k-1)\le n$；
• 所有测试数据中 $n$ 的总和不超过 $10^5$；
• 所有测试数据中 $q$ 的总和不超过 $2\times 10^5$。