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

庆功宴上，$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

样例三

见附件下载。

数据范围与提示

对于所有数据，$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}$