시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB28713511349.130%

문제

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

예제 입력 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

힌트

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$