UOJ Logo Universal Online Judge

UOJ

附件下载 统计

得胜归来的黄忠准备举办一场庆功宴。

庆功宴上,$p$ 个士兵围着圆桌坐成一圈,并按顺时针顺序依次编号为 $1, 2, \cdots, p$。

根据计划,他们会进行 $q$ 次合唱,合唱内容为汉高祖刘邦所作的《大风歌》,以坚定复兴汉室的理想信念。

为了活跃气氛,黄忠会使用一种看似随机的方式决定参与合唱的人选。每次合唱前,黄忠会选择三个整数 $x, k, l$ 并从第 $x$ 个士兵开始沿顺时针方向 $1, 2, \cdots, k$ 循环报数。前 $l$ 个报到 $k$ 的士兵会参加此次合唱。为保证所有合唱都能顺利进行,士兵总数 $p$ 是素数。可以证明当 $1 \le k < p$ 时,前 $p$ 个报到 $k$ 的士兵各不相同。

刘备也打算参加庆功宴。他认为编号为 $i$ 的士兵唱《大风歌》的美妙度为 $a_i$,而一次合唱的美妙度为所有演唱者的美妙度之和。现在他知道了每次合唱 $x, k, l$ 的值,并希望你算出对应的美妙度,以便最优化听歌体验。

输入格式

第一行,两个正整数 $p, q$。

第二行,$p$ 个正整数,其中第 $i$ 个为 $a_i$。

接下来的 $q$ 行,每行三个正整数,依次为每次合唱对应的 $x, k, l$。

输出格式

$q$ 行,每行一个整数,依次为每次合唱的美妙度。

样例一

input

3 5
4 5 3
3 1 3
1 1 1
3 1 3
2 1 2
1 2 3

output

12
4
12
8
12

explanation

第 $1$ 次合唱选中的士兵编号依次为 $3, 1, 2$,美妙度之和为 $3 + 4 + 5 = 12$。

第 $2$ 次合唱选中的士兵编号为 $1$,美妙度之和为 $4$。

第 $3$ 次合唱选择士兵的过程与第一次完全相同。

第 $4$ 次合唱选中的士兵编号依次为 $2, 3$,美妙度之和为 $5 + 3 = 8$。

第 $5$ 次合唱选中的士兵编号依次为 $2, 1, 3$,美妙度之和为 $5 + 4 + 3 = 12$。

样例二

input

7 10
1 9 8 6 7 2 9
4 4 7
3 6 4
5 5 3
7 2 1
4 1 2
4 4 4
1 6 6
7 4 3
4 2 6
6 1 2

output

42
19
25
1
13
23
33
23
34
11

样例三

见附件下载。

数据范围与提示

子任务编号 $p \leq$ $q \leq$ 特殊性质 分值
$1$ $1000$ $1000$ $10$
$2$ $10^5$ $10^5$ $a_i = i$ $10$
$3$ $10^5$ $10^5$ $k \leq 100$ $10$
$4$ $10^5$ $10^5$ $25$
$5$ $3 \times 10^5$ $3 \times 10^5$ $45$

对于所有数据,$1 \leq p, q \leq 3 \times 10^5$,$1 \leq a_i \leq 10^9$;$1 \leq x, l \leq p$,$1 \leq k < p$;保证 $p$ 为素数。

提示

请选手注意程序实现时的常数因子。

时间限制:$\texttt{3s}$

空间限制:$\texttt{1GB}$