Migrated from Lutece 2745 省时度日

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你现在被安排在一个工厂内进行监工。你底下有着 $n$ 个工人，他们有一个习惯，就是喜欢在他们的仪器上用不同记号标记上当天的工作量。工人 $i$ 初始的工作量为 $A_i$ ，你喜欢用一个表来记录他们每个人工作量最少的时候的工作量是多少，工人 $i$ 工作量最少的一天的工作量为 $B_i$。

在接下来的 $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$ 的最小值。

显然每个工人的工作量最少的时候的工作量是在动态变化的，因此每天你都会更新 $B_i$ ,令所有的 $B_i$ 变为 $\min(B_i,A_i)$。

现在为了知道每天工人的工作量和工作量最少的时候的工作量，所以你想编写一个程序来动态实现这一过程。

Input

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

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

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

若 $opt_i=1$ ，则接下来三个整数 $l,r,c$ ,表示操作一。

若 $opt_i=2$ ，则接下来三个整数 $l,r,d$ ,表示操作二。

若 $opt_i\geq3$ ，则接下来两个整数 $l,r$ ,表示操作三，四。

Output

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

Samples

3 6
1 2 3
4 3 3
1 2 3 -2
3 1 3
4 3 3
2 2 3 4
3 1 3

3
0
1
1

Constraints

对于所有数据

$1\le n,m \le 5\times 10^5 ,1 \le l\le r \le n,−2000 \le c \le 2000$

$−10^9 \le A_i,d \le 10^9$

Resources

2022 UESTC ICPC Training for Data Structures