问题陈述

给定一个整数序列 $a_0, a_1, ..., a_{N-1}$。

你需要执行 $Q$ 个查询，每个查询可以是以下之一：

• ADD QUERY(t=0 l r x)：对于每个介于 $l$ 和 $r$ 之间（包括）的 $i$，将 $a_i$ 替换为 $a_i + x$。
• DIV QUERY(t=1 l r x)：对于每个介于 $l$ 和 $r$ 之间（包括）的 $i$，将 $a_i$ 替换为 ${\\rm floor}(a_i / x)$，其中 ${\\rm floor}(y)$ 是不大于 $y$ 的最大整数。
• MAX QUERY(t=2 l r x=0)：打印 ${\\rm max}(a_l, a_{l+1}, ..., a_r)$。
• RESTORE QUERY(t=3 l r x=0)：对于每个介于 $l$ 和 $r$ 之间（包括）的 $i$，将 $a_i$ 设置为初始值，即输入中给出的值。

约束条件

• 所有输入值都是整数。
• $1 \\leq N, Q \\leq 200,000$
• $0 \\leq a_i \\leq 10^8$
• $t_i = 0, 1, 2, 3$
• $0 \\leq l_i \\leq r_i \\leq N-1$
• $1 \\leq x_i \\leq 1000$（当 $t_i \\neq 2, 3$）

输入

输入以以下格式从标准输入给出：

$N$ $Q$ $a_0$ $a_1$ ... $a_{N-1}$ $t_1$ $l_1$ $r_1$ $x_1$ $t_2$ $l_2$ $r_2$ $x_2$ ： $t_Q$ $l_Q$ $r_Q$ $x_Q$

输出

对于每个 MAX QUERY，打印 ${\\rm max}(a_l, a_{l+1}, ..., a_r)$，每行一个。

示例输入 1

5 9
1 2 3 4 5
2 0 4 0
0 0 1 10
2 0 4 0
2 2 2 0
1 0 1 4
2 0 0 0
2 1 1 0
3 0 4 0
2 0 1 0

示例输出 1

5
12
3
2
3
2

• ${\\rm max}(1, 2, 3, 4, 5) = 5$
• $1, 2, 3, 4, 5 → 11, 12, 3, 4, 5$
• ${\\rm max}(11, 12, 3, 4, 5) = 12$
• ${\\rm max}(3) = 3$
• $11, 12, 3, 4, 5 → 2, 3, 3, 4, 5$
• ${\\rm max}(2) = 2$
• ${\\rm max}(3) = 3$
• 数组恢复为 $1, 2, 3, 4, 5$
• ${\\rm max}(1, 2) = 2$

示例输入 2

4 7
0 1 0 1
2 0 3 0
0 0 3 1
1 0 3 2
2 0 3 0
0 0 3 1
1 0 3 2
2 0 3 0

示例输出 2

1
1
1

示例输入 3

10 23
13 1 22 8 28 18 23 9 22 27
1 3 4 5
1 8 8 8
0 3 9 5
0 2 6 3
3 0 4 0
1 1 3 7
2 2 2 0
2 3 5 0
0 1 4 2
3 0 9 0
2 0 1 0
0 3 9 8
2 1 9 0
0 8 9 5
1 5 7 7
0 3 5 7
0 7 9 7
3 3 6 0
2 1 6 0
0 1 1 7
1 4 8 10
2 0 9 0
1 5 6 1

示例输出 3

3
28
13
36
28
47