Хель

시간 제한4초메모리 제한1024 MB

요약

각 질의마다 구간에서 한 원소를 골라 k를 곱했을 때, 구간 절댓값 합이 가질 수 있는 최댓값을 구한다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

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

Все ее узники стоят в ряд и занумерованы от 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>> выведите максимальную боль отрезка, которую можно получить.

힌트

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

예제2

예제 1
입력
```
3
1 2 3
2
assign 2 4
torture 2 3 3
```
예상 출력
```
15
```

예제 2

입력

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

예상 출력