给定一个整数序列 $a_0, a_1, \dots, a_{N-1}$。 你需要执行 $Q$ 次查询，每次查询属于以下类型之一：

• ADD $t = 0, l, r, x$：对于所有满足 $l \le i \le r$ 的 $i$，令 $a_i = a_i + x$。
• DIV $t = 1, l, r, x$：对于所有满足 $l \le i \le r$ 的 $i$，令 $a_i = \lfloor a_i/x \rfloor$，其中 $\lfloor y \rfloor$ 表示不超过 $y$ 的最大整数。
• MAX $t = 2, l, r, x=0$：输出 $\max(a_l, a_{l+1}, \dots, a_r)$。

输入格式

输入按以下格式给出：

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

数据范围

所有输入值均为整数，$1 \le N, Q \le 200\,000$，$0 \le a_i \le 10^8$，$t_i \in \{0, 1, 2\}$，$0 \le l_i \le r_i \le N - 1$。 若 $t_i \neq 2$，则 $1 \le x_i \le 1000$；若 $t_i = 2$，则 $x_i = 0$。

输出格式

对于每个 MAX 查询，输出 $\max(a_l, a_{l+1}, \dots, a_r)$。

样例

输入 1

5 7
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

输出 1

5
12
3
2
3

输入 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 20
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
1 1 3 7
2 2 2 0
2 3 5 0
0 1 4 2
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
2 1 6 0
0 1 1 7
1 4 8 10
2 0 9 0
1 5 6 1

输出 3

3
26
13
40
30
52

说明

对于样例 1： $\max(1, 2, 3, 4, 5) = 5$ $1, 2, 3, 4, 5 \to 11, 12, 3, 4, 5$ $\max(11, 12, 3, 4, 5) = 12$ $\max(3) = 3$ $11, 12, 3, 4, 5 \to 2, 3, 3, 4, 5$ $\max(2) = 2$ $\max(3) = 3$