\begin{problem}{RMQ}{rmq.in}{rmq.out}{1 секунда}{64 мегабайта}

Дан массив $\texttt{a[1..n]}$. Требуется написать программу, обрабатывающую два типа запросов.
\begin{itemize}
  \item Запрос ``$\texttt{max} \; l \; r$''. Требуется найти максимум в массиве $\texttt{a}$ от $l$-ой ячейки до $r$-ой включительно.
  \item Запрос ``$\texttt{add} \; l \; r \; v$''. Требуется прибавить значение $v$ к каждой ячейке массива $\texttt{a}$ от $l$-ой до $r$-ой включительно.
\end{itemize}


\InputFile
Первая строка содержит два целых числа $n$ и $q$ ($1 \leq n, q \leq 10^5$) -- длина массива и число запросов соответственно. Второая строка содержит $n$ целых чисел $a_1, \dots, a_n$ ($|a_i| \leq 10^5$), задающих соответствующие значения массива. Следующие $q$ строк содержат запросы. 

В зависимости от типа запрос может иметь вид либо ``$\texttt{max}\;l\;r$'', либо ``$\texttt{add}\;l\;r\;v$''. При этом $1 \leq l \leq r \leq 10^5$, $|v| \leq 10^5$.

\OutputFile
Для каждого запроса вида ``$\texttt{max} \;l\;r$'' требуется в отдельной строке выдать значение соответствующего максимума.

\Examples

\begin{example}
\exmp{5 3
1 2 3 4 -5
max 1 3
add 1 2 5
max 1 3
}{3
7
}%
\end{example}

\end{problem}
