Problem Description

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 QUERY(t=0 l r x): for each \( i \) between \( l \) and \( r \), inclusive, replace \( a_i \) with \( a_i + x \).
• DIV QUERY(t=1 l r x): for each \( i \) between \( l \) and \( r \), inclusive, replace \( a_i \) with \( \text{floor}(a_i / x) \), where \( \text{floor}(y) \) is the largest integer not greater than \( y \).
• MAX QUERY(t=2 l r x=0): print \( \text{max}(a_l, a_{l+1}, \ldots, a_r) \).
• RESTORE QUERY(t=3 l r x=0): for each \( i \) between \( l \) and \( r \), inclusive, set \( a_i \) to the initial value of \( a_i \), that is, the value given in the input.

Input Format

Input is given from Standard Input in the following format:

\( N \) \( Q \) \( a_0 \) \( a_1 \) \ldots \( 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 \)

Output Format

For each MAX QUERY, print \( \text{max}(a_l, a_{l+1}, \ldots, a_r) \), one per line.

Sample Input and Output

Sample Input #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

Sample Output #1

5
12
3
2
3
2

Sample Input #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

Sample Output #2

1
1
1

Sample Input #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

Sample Output #3

3
28
13
36
28
47

Notes/Hints

Constraints

• All input values are integers.
• \( 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 \) (when \( t_i \neq 2, 3 \))

Sample Explanation 1

• \( \text{max}(1, 2, 3, 4, 5) = 5 \)
• \( 1, 2, 3, 4, 5 \rightarrow 11, 12, 3, 4, 5 \)
• \( \text{max}(11, 12, 3, 4, 5) = 12 \)
• \( \text{max}(3) = 3 \)
• \( 11, 12, 3, 4, 5 \rightarrow 2, 3, 3, 4, 5 \)
• \( \text{max}(2) = 2 \)
• \( \text{max}(3) = 3 \)
• The array is restored to \( 1, 2, 3, 4, 5 \)
• \( \text{max}(1, 2) = 2 \)

见题面 Input 部分

见题面 Output 部分