29252번 - Хель 다국어

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

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

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

В первой строке дано число $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$ строках следуют запросы вида

• <<assign>> $x$ $t$ ($1 \le x \le n$, $-10^8 \le t \le 10^8$) --- заменить температуру узника с номером $x$ на $t$
• <<torture>> $l$ $r$ $k$ ($1 \le l \le r \le n$, $-10^8 \le k \le 10^8$) --- начать мучить отрезок, начиная с узника с номером $l$ и заканчивая узником с номером $r$, умножив температуру одного из узников этого отрезка на $k$

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

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