小Z的加油店

内存限制：256 MiB 时间限制：10 Sec

小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子，每个瓶子有一个容量vi。每次别人来加油，他会让

别人选连续一段的瓶子。他可以用这些瓶子装汽油，但他只有三种操作：

1.把一个瓶子完全加满；

2.把一个瓶子完全倒空；

3.把一个瓶子里的汽油倒进另一个瓶子，直到倒出瓶子空了或者倒进的瓶子满了。

当然，为了回馈用户，小Z会时不时选择连续一段瓶子，给每个瓶子容积都增加x。

为了尽可能给更多的人加油，每次客户来加油他都想知道他能够倒腾出的汽油量最少是多少？

当然他不会一点汽油都不给客户。

第一行包括两个数字：瓶子数n，事件数m。

第二行包含n个整数，表示每个瓶子的容量vi。

接下来m行，每行先有三个整数fi li ri。

若fi=1表示询问li到ri他最少能倒腾出的汽油量最少是多少？

若fi=2 再读入一个整数x。表示他将li到ri的瓶子容量都增加了x。

1 <= n,m <= 10^5 , 1<=li<=ri<=n , 1<=初始容量,增加的容量<=1000

对于每个询问输出对应的答案

有可能出现L>R,读入的p不只有0和1，把所有非1操作当成2才能AC

#5028. 小Z的加油店