ADD, DIV, MAX

정수 수열 $a_0, a_1, \ldots, 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 = {\rm floor}(a_i / x)$. 여기서 ${\rm floor}(y)$는 $y$보다 크지 않은 가장 큰 정수이다.
• MAX $t=2$, l r x=0: ${\rm max}(a_l, a_{l+1}, \ldots, a_r)$을 출력한다.

입력은 다음 형식으로 주어진다.

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

$\ldots$

$t_Q$ $l_Q$ $r_Q$ $x_Q$

각 MAX 질의에 대해 ${\rm max}(a_l, a_{l+1}, ..., a_r)$을 출력한다.

모든 입력값은 정수이며, $1 \leq N, Q \leq 200\,000$, $0 \leq a_i \leq 10^8$, $t_i = 0, 1, 2$, $0 \leq l_i \leq r_i \leq N-1$, $t_i \neq 2$이면 $1 \leq x_i \leq 1000$, $t_i=2$이면 $x_i=0$이다.

예제 1에 대해,

${\rm max}(1, 2, 3, 4, 5) = 5$

$1, 2, 3, 4, 5 \to 11, 12, 3, 4, 5$

${\rm max}(11, 12, 3, 4, 5) = 12$

${\rm max}(3) = 3$

$11, 12, 3, 4, 5 \to 2, 3, 3, 4, 5$

${\rm max}(2) = 2$

${\rm max}(3) = 3$