背景

“有一件事我想问你……”白苌忽然对姬野说，“你觉得未来是能被改变的么？"
“能，假如改变本身即是未来的一部分的话。”
“是么……”白苌轻声说。------九州

既然世界要与我为敌，我便覆这天下，灭这苍生！！------天驱副宗主Achen

描述

天启八年六月 屠龙关外
“只要最后一个天驱还活着，总有人不敢暴露他们的野心！”首领仰天吼叫，“铁甲……”“依然在！”所有人都随着他咆哮。
“铁甲！！依然在！！”“铁甲！！！”“依然在！！！”“回北方去！”
首领高呼着。数百支火把一起点燃。鹰旗所指，一道火流在荒原上飞驰起来，向着北方发起了最后一次冲锋.

眼前的壮烈场面让Achen震惊了，慌乱中得知自己来到了九州。看着眼前的天驱一个个倒下，善良的Achen于心不忍，想要通过毕生所学来帮助他们，望向远方，整个屠龙关已被分为了大大小小共计N个战场，每个战场时有A[i]个天驱武士在作战，但毕竟人单事薄，所以Achen想要合理调配各个战场上的人数，从而达到以少胜多的奇效.

已知Achen制定了两个即时的方案，分别为1.将L-R内的战场上分配的天驱武士数依次改为min（x，A[i]），从而更好保证有生实力（注意x给定）；2.询问传令员KEKE_046 L-R内的战场上一共有多少天驱武士仍在奋战.

现在想一想你就是那个倒霉的传令员KEKE_046，你会怎么办？

格式

输入格式

第一行包含两个正整数，表示N个战场与Achen指令数M。（1<=n,m<=300000）
接下来N个整数，表示每个战场的初始天驱武士数（正整数）
接下来M行每行一个指令（具体见题目描述）

输出格式

对于Achen每一个2指令你需要输出一个正整数

样例1

样例输入1

10 6
1690796 481111 122343 1009541 1192673 684946 1978408 1006437 1378470 329692 
2 6 9
1 7 10 1070273
2 6 10
1 5 9 176604
1 9 10 693701
2 5 6

样例输出

5048261
4161621
353208

限制

每个测试点1s

提示

输入数据规模较大请合理使用（“慢读”）
注意使用long long

后记

天启八年五月，慕容毅被指控意图篡位，于午门斩首。慕容家被满门抄斩，所有佩戴天驱指环者，皆判定为有叛国之罪。
天启八年六月，诸侯围歼天驱众武士与屠龙关外，天驱几近覆没，活下来只有一个突然出现的少年Achen与未来的野尘军首领姬野.
天启九年一月,Achen再战天启城，铁甲依然在！

来源

Summer_Wang改编自Picks loves Segment trees