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

庆功宴上，$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\le p,q\le 3\times {10}^5$，$1\le a_i\le {10}^9$；$1\le x,l\le p$，$1\le k<p$；保证 $p$ 为素数。

提示

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

时间限制：$\mathtt{\text{3s}}$

空间限制：$\mathtt{\text{1GB}}$