2900. 苦恼的Van

【题目描述】

Van最近很苦恼，因为他的平家boy们都太过强大了，Van深感力不从心。恰巧Van的朋友木吉刚从新日暮里回来，学会了一些膜法，当Van和木吉谈起自己的苦恼时，木吉表示愿意用自己的膜法帮Van解决问题。

Van的平家boy们都身经百战，有一腚的力量值，居住在与Van相邻的平坦的街道上。木吉的膜法可以使boy们的力量值小于等于p，具体做法是通过摸（%），木吉在释放膜法的同时也会使用鬼步来让膜法的效率更高，即木吉会通过鬼步来完成瞬移，使他能够同时摸一段街道上的boy们。但由于木吉的鬼步非常骚皮，所以他的膜法会受到影响，即p值具有极大的不稳定性，对于每一段街道，里面的boy们受到的抚摸都会变化。

现在，木吉找到Van来汇报自己的鬼步，但是Van却忙着教训自己的平家boy们，于是Van就把这个任务交给了因为超速而被跤警Van拘留的你，但是Van为了调教你，同时想知道自己能否战胜那些平家boy们，就把自己的问题掺杂在木吉的鬼步中。作为王的我为了让你好好的接受Van的调教，就帮助你把Van的问题和木吉的鬼步分开，即0代表Van的问题，1代表木吉的鬼步。

【输入格式】

第一行两个整数n m，n代表平家boy们的数量，m代表木吉的鬼步和Van的问题的总数量。

接下来n行，每行一个整数代表一个平家boy的力量值；

接下来m行，每行一个操作，有如下两种情况：

0 a b   代表Van想让你告诉他当前从a到b（包含a b）的平家boy们的力量值的和；

1 a b p  代表木吉的鬼步是从a到b的瞬移，p的含义见题目描述。

【输出格式】

对于每一个Van的询问，输出平家boy们的力量值的和。

【样例输入】

2 2

 5 

 7

 1 1 2 3

 0 1 2

【样例输出】

3

【提示】

 Van的平家boy们数量众多，但尻虑到木吉的感受，Van只要求他最多对100000只平家boy施展膜法。对于Van的每次询问和木吉的每次膜法，都有0<a<=b<=100000。同时木吉受到鬼步的强大影响最多释放100000膜法（包含Van的询问）。

【来源】

 新日暮里唱片公司