ADD, DIV, MAX

You are given an integer sequence $a\_0, a\_1, \ldots, a\_{N-1}$.

You have to perform $Q$ queries, each query is one of the following:

• ADD $t=0$, l r x: for each $i$ between $l$ and $r$ inclusively, $a\_i = a\_i + x$.
• DIV $t=1$, l r x: for each $i$ between $l$ and $r$ inclusively $a\_i = {\rm floor}(a\_i / x)$, where ${\rm floor}(y)$ is the biggest integer that is not greater than $y$.
• MAX $t=2$. l r x=0: print ${\rm max}(a\_l, a\_{l+1}, \ldots, a\_r)$.

Input is given in the following format:

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

For each MAX query, print ${\rm max}(a\_l, a\_{l+1}, ..., a\_r)$.

All input values are integers, $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$, $1 \leq x\_i \leq 1000$ if $t\_i \neq 2$, $x\_i=0$ if $t\_i=2$.

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