Задано два целочисленных массива \(a\) и \(b\), оба размера \(n\).
Скажем, что стоимость подотрезка массива \([l, r]\) равна \(a_l + a_{l + 1} + \cdots + a_{r - 1} + a_r + b_l + b_r\). Если \(l=r\), то стоимость равна \(a_l + 2 \cdot b_l\).
Вам предстоит отвечать на запросы трех видов:
- «\(1\) \(p\) \(x\)» — присвоить \(a_{p} := x\);
- «\(2\) \(p\) \(x\)» — присвоить \(b_{p} := x\);
- «\(3\) \(l\) \(r\)» — найти два непустых непересекающихся подотрезка у отрезка \([l, r]\) с максимальной суммарной стоимостью и вывести их суммарную стоимость.
Выходные данные
Для каждого запроса третьего типа выведите максимально возможную суммарную стоимость двух непустых непересекающихся подотрезков у отрезка \([l, r]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 -1 4 -3 2 4 0
0 6 1 0 -3 -2 -1
6
3 1 7
1 2 0
3 3 6
2 5 -3
1 3 2
3 1 5
|
18
7
16
|
|
2
|
10
2 -1 -3 -2 0 4 5 6 2 5
2 -4 -5 -1 6 2 5 -6 4 2
10
3 6 7
1 10 -2
3 5 7
3 2 8
2 1 -5
2 7 4
3 1 3
3 3 8
3 2 3
1 4 4
|
23
28
28
-17
27
-22
|