Background

splay裸题

Description

给定一个序列，支持区间加，区间翻转，区间查询最大值。

Format

Input

第一行两个整数N，M。N为序列长度，M为操作数。
以下M行，每行一个opt
opt=1，区间加，[L,R]加x；
opt=2，区间翻转，翻转[L,R]；
opt=3，区间球最大，球[L,R]最大值。

Output

对于每个opt=3，一行一个数表示ans。

Sample 1

Input

2 1
1 2
3 1 2

Output

2

Limitation

2s，233MB

Hint

对于50%的数据，n<=10000；
对于100%的数据，n<=300000。