派蒙的藏宝图
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一天，贪财的派蒙发现了一张藏宝图，图上有 n 个传送锚点，去往第 i 个传送锚点可以获得 a[i] 个纠缠之缘，但是在地图上这 n 个传送锚点按顺序形成了一个环，只能顺时针或者逆时针走向下一个相邻的传送锚点，（因为是一个环，第n号传送锚点下一个应该是 1 号传送锚点），派蒙现在有了一个问题，如果起点在第 p 号传送锚点，给定行动方向 d(1为顺时针，-1为逆时针)，按方向走动 k 步，一共可以获得多少纠缠之缘，起点的纠缠之缘将直接获得。
由于派蒙是应急食品，很笨很笨，所以她想请教聪明的旅行者你，相信你一定能很快回答出这个问题！
每个传送瞄点的纠缠之缘供应是无限的。每次路过都可以拿走a[i]个。

输入描述:

第一行输入两个正整数 n,m，分别代表传送锚点的个数以及询问次数。
第二行输入n个正整数 a[i], 代表走到第 i 个传送锚点可以获得的纠缠之缘个数。
接下来m行,每行输入3个正整数 d,p,k,分别代表走的方向，起点位置，以及走的步数。
ps ：d为1代表顺时针，d为-1代表逆时针。

输出描述:

对于m次询问，每行输出一个整数，代表最后可以获得的纠缠之缘数，保证所有输出在long long 范围内
示例1

输入

复制 
5 3
1 2 3 4 5
1 1 3
1 4 3
-1 4 2

输出

复制 
10
12
9

说明

对于第一次询问   顺时针方向，从1号传送锚点出发，走3步，到达4号(1-2-3-4)纠缠之缘数为1+2+3+4=10
对于第二次询问，顺时针方向，从4号传送锚点出发，走3步，到达2号(4-5-1-2)纠缠之缘数为4+5+1+2=12
对于第三次询问，逆时针方向，从4号传送锚点出发，走2步，到达2号(4-3-2)纠缠之缘数为4+3+2=9