零点的钟声马上就要敲响，2016 年即将要拉开序幕，元旦老人轻手轻脚地来到了 picks 的床头，准备把他的礼物装进袜子里。

然而，picks 居然根本没有去睡觉！毫无防备的元旦老人落入了他的陷阱之中。

原来，picks 仰慕正义的元旦老人已经很久了，于是他决定把元旦老人抓来探♂讨哲♂学（病娇脸）。

在经过交涉之后，picks 答应，如果元旦老人能回答出他的一些问题，那么就放他走：

最开始 picks 有三个长度为 $n$ 的完全相同的数列 $A,B$ 和 $C$，接下来有 $m$ 次操作，每一次操作都是以下的六种之一：

1. 对于所有的 $i\in [l,r]$，将 $A_i$ 变成 $A_i+c$。
2. 对于所有的 $i\in [l,r]$，将 $A_i$ 变成 $max(A_i,d)$。
3. 对于所有的 $i\in [l,r]$，询问 $A_i$ 的最小值。
4. 对于所有的 $i\in [l,r]$，询问 $B_i$ 的最小值。
5. 对于所有的 $i\in [l,r]$，将 $A_i$ 变成 $min(A_i,e)$。
6. 对于所有的 $i\in [l,r]$，询问 $C_i$ 的最大值。

在每一次操作结束之后，picks 都会进行一次更新：对于所有的 $i\in [1,n]$，将 $B_i$ 变成 $min(B_i,A_i)$，$C_i$ 变成 $max(C_i,A_i)$。

然而留给元旦老人的时间已经所剩无几了，情急之下，他决定向你寻求帮助：你能帮他回答 picks 的问题吗。

输入格式

第一行两个数：$n,m$。

接下来一行 $n$ 个数 $A_i$。（最开始 $A_i=B_i=C_i$）

接下来 $m$ 行中，第 $i$ 行第一个数 $t_i$ 表示操作类型：

若 $t_i=1$，则接下来三个整数 $l_i,r_i,c_i$，表示操作一。

若 $t_i=2$，则接下来三个整数 $l_i,r_i,d_i$，表示操作二。

若 $t_i=3$，则接下来三个整数 $l_i,r_i$，表示操作三。

若 $t_i=4$，则接下来一个整数 $l_i,r_i$，表示操作四。

若 $t_i=5$，则接下来三个整数 $l_i,r_i,e_i$，表示操作五。

若 $t_i=6$，则接下来一个整数 $l_i,r_i$，表示操作六。

输出格式

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

样例一

input

3 6
1 2 3
4 3 3
1 2 3 -2
5 1 3 0
4 3 3
2 2 3 4
4 1 3

output

3
0
0

样例二

见附件下载。

限制与约定

对于所有数据，保证有 $1\le n,m\le 5\times {10}^5,1\le l_i\le r_i\le n,-2000\le c_i\le 2000$ 和 $-{10}^9\le A_i,d_i,e_i\le {10}^9$

保证在任意时刻序列中的值在 int 范围内。

时间限制：$6\mathtt{\text{s}}$

空间限制：$128\mathtt{\text{MB}}$