\begin{problem}{Хель}{hel.in}{hel.out}{4 секунды}{256 мегабайт}
                                                                    
%Автор задачи: Нияз Нигматуллин
%Автор условия: Никита Кравцов

Хель~--- владычица мертвых, одна половина ее лица кроваво-красная, другая же 
иссиня-черная. В связи с комплексом неполноценности, развившемся из-за такой 
внешности, она очень любит издеваться над своими узниками.

Все ее узники стоят в ряд и занумерованы от 1 до $n$. Каждый узник имеет 
свою температуру, при которой он в данный момент мучается. Хель может в 
любой момент поменять температуру любого узника на некоторую другую. 

Иногда Хель решает кратковременно помучить конкретный 
отрезок. При этом она умножает на $k$ температуру одного из узников 
на отрезке. После этого мучения температура этого узника снова придет к 
первоначальной. При этом \textit{боль} отрезка вычисляется как сумма модулей 
температур каждого узника на этом отрезке. Теперь Хель хочется максимально 
увеличить \textit{боль} каждого отрезка, который она захотела помучить.

\InputFile
В первой строке дано число $n$ ($1 \le n \le 300\,000$)~--- количество узников.
Во второй строке находятся $n$ чисел $a_i$ ($-10^8 \le a_i \le 10^8$)~--- температура i-го узника.
В третьей строке находится число $m$ ($1 \le n \le 300\,000$)~--- количество запросов.
Далее в $m$ строках следуют запросы вида 
\begin{itemize}
   \item <<\texttt{assign}>> $x$ $t$ ($1 \le x \le n$, $-10^8 \le t \le 10^8$)~--- заменить температуру узника с номером $x$ на $t$
   \item <<\texttt{torture}>> $l$ $r$ $k$ ($1 \le l \le r \le n$, $-10^8 \le k \le 10^8$)~--- начать мучить отрезок, начиная с узника с номером $l$ и заканчивая узником с номером $r$,
   умножив температуру одного из узников этого отрезка на $k$
\end{itemize}


\OutputFile
Для каждого запроса <<\textit{torture}>> выведите максимальную \textit{боль} отрезка, которую можно получить.

\Examples
\begin{example}%
\exmp{
3
1 2 3
2
assign 2 4
torture 2 3 3
}{
15
}%                                                                                                                `
\exmp{
6
-1 -6 0 5 3 -3
9
assign 1 -9
torture 1 1 7
assign 2 9
torture 1 2 -9
torture 3 5 -6
torture 3 6 0
assign 3 -1
torture 5 6 9
torture 6 6 0
}{
-63
99
5
8
27
0
}%                                                                                                                `
\end{example}

\Note
В первом примере Хель выгодно умножить на три температуру второго узника.

\end{problem}
