Background

线段树模板题

Description

给定一个长度为n的序列，支持区间加，区间查询最大值。

Input

第一行两个数n，m表示序列长度和操作次数。
下一行n个数表示原始序列A。
下面m行，每行一个opt，
opt=1是区间加操作，接下来三个数L,R,x，表示[L,R]区间加上x；
opt=2是区间查询最大值，接下来两个数L,R表示区间[L,R]。

Output

对于每个询问，输出一行表示答案。

Sample 1

Input

2 2
1 2
1 1 1 3
2 1 2

Output

4

Limitation

1s，512MB

Hint

对于20%的数据，n<=5000,m<=5000;
对于60%的数据，n<=50000,m<=50000;
对于100%的数据，n<=500000,m<=500000。
操作中区间加中的|x|<=1000，原始序列|A[i]|<=1000。