#1302. [ONTAK2015]Stumilowy sad

[ONTAK2015]Stumilowy sad

Description

在一条笔直的道路上从左到右一共有n片区域,每一片区域一开始都种着一棵树,其中第i片区域种着高度为h[i]的树。接下来你需要处理q个操作:

1 l r c : 将第l片区域到第r片区域内的所有树的高度拔高c(|c|<=500)个单位。

2 l r h : 将一把刀固定在高度为h(1<=h<=10^9)的空中,对第l片区域到第r片区域内的所有树进行砍伐。

3 l r h : 往第l片区域到第r片区域内的每个区域种上一棵高度为h(1<=h<=10^9)的树。

4 l r : 查询第l片区域到第r片区域内最高的树的高度。

注意:本题中的高度为相对于某个水平面的高度,也就是说可能会有负数的出现。

Format

Input

第一行包含两个正整数n,q(1<=n,q<=500000),分别表示区域数和操作数。

第二行包含n个正整数,其中第i个数表示hi

接下来q行依次描述每一个操作。

Output

输出若干行,每行一个整数,对于每次查询输出相应的结果。

Samples

2 5
3 7
4 1 2
1 1 2 1
4 1 2
3 1 1 5
4 1 2
7
8
8