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范围内

题解

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