考虑包含了$n$个元素的序列$a$。我们希望你实现一个数据结构，支持如下的两个操作：

1. 给定区间$[l,r]$，你需要把该区间内每个元素都加上$x$。
2. 求给定区间$[l,r]$的最大值。

输入格式

第一行是两个整数，$n$和$q$，$n$表示序列长度，$q$表示操作个数。

第二行是$n$个数，表示序列$a$的初始值。

之后$q$行，每行表示一个操作。在一个操作中，第一个数字表示操作类型，为$1$或$2$，意义见上。之后两个数字表示区间$l$和$r$。如果操作类型为$1$，则后面还有第三个数字表示$x$。

范围保证$1 \le n, q \le 10^6$，每个$0\le a_i \le 10^9$，每个操作中$1\le l \le r \le n$，并且$0 \le x \le 10^9$。

输出格式

对于每个类型$2$的操作，输出其查询结果并换行。

样例输入

10 5
1084 7673 13201 31375 15797 23954 27905 12498 4468 9210
1 4 10 24291
2 1 10
1 6 7 19422
2 1 10
2 4 8

样例输出

55666
71618
71618

注意因为评测机太慢本题时间限制6s