【codecomb2098】stone

2014年10月16日1,2030

Description

n个石堆围成一圈,提供两种操作:

1、每次将[L,R]堆的石子数量+k,其中,1<=L,R<=n,k>=0。

2、询问有最多石子的那一堆有多少石子。

现在,要求在线解决该问题。

Input

第一行两个整数n和m,n表示石子圈的长度,m表示操作数量。

以下m行,首先一个是整数t,t=1或2,表示是哪种操作。 如果t=1,则后面跟三个整数l,r,k,表示区间[l,r]的所有石子堆石子数量+k,如果t=2表示上述询问操作。

 

Output

 

对于每一个询问,输出石子数量。

 

Sample Input

3 3

1 1 2 1

1 3 1 2

2

Sample Output

3

Hint

数据范围:

10%的数据m<=1000

40%的数据n<=100000

100%的数据n<2^32,m<=100000

答案保证在longint范围内

题解

用动态开点的线段树就水过了嘛。。标记永久化会比较不虚