AT_jag2018summer_day2_i ADD DIV MAX RESTORE

[problemUrl]: https://atcoder.jp/contests/jag2018summer-day2/tasks/jag2018summer_day2_i You are given an integer sequence $ a_0,\ a_1,\ ...,\ 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 $ {\rm\ floor}(a_i\ /\ x) $, where $ {\rm\ floor}(y) $ is the biggest integer that is not greater than $ y $. - `MAX QUERY(t=2 l r x=0)` : print $ {\rm\ max}(a_l,\ a_{l+1},\ ...,\ 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 is given from Standard Input 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 $ : $ t_Q $ $ l_Q $ $ r_Q $ $ x_Q $

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

### 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 \- $ {\rm\ max}(1,\ 2,\ 3,\ 4,\ 5)\ =\ 5 $ - $ 1,\ 2,\ 3,\ 4,\ 5\ →\ 11,\ 12,\ 3,\ 4,\ 5 $ - $ {\rm\ max}(11,\ 12,\ 3,\ 4,\ 5)\ =\ 12 $ - $ {\rm\ max}(3)\ =\ 3 $ - $ 11,\ 12,\ 3,\ 4,\ 5\ →\ 2,\ 3,\ 3,\ 4,\ 5 $ - $ {\rm\ max}(2)\ =\ 2 $ - $ {\rm\ max}(3)\ =\ 3 $ - The array is restored to $ 1,\ 2,\ 3,\ 4,\ 5 $ - $ {\rm\ max}(1,\ 2)\ =\ 2 $