小z在做数据统计，他面前有n个数字，数据给定了范围m，也就是数字只在0 \dots m-1之间；
现在给定k次操作，给出三个数字op,x,y；
如果op=1的话，那么它会把a_x增加y，但是这个数字不会超过m，因为一旦超过m，变成0后，重新增加，例如$m=4,a[3]=2,$增加$3$,它就变成了$1$；
如果op=2的话，请你给出x~y区间内的和
第一行两个数字n,m;
接下来给出n个数字a_i;
接下来一个数字k;
接下来k行，每行三个数字op,x,y
针对op=2的输出区域的和
5 3 0 1 2 0 1 5 2 1 3 1 1 2 2 1 3 1 4 5 2 1 5
3 5 8
40\%的数据，n,m,k\leq2000
100\%的数据，n,m,k\leq500000
| Time Limit | 1 second |
| Memory Limit | 128 MB |