Рассмотрим последовательность целых чисел a1, a2, ..., an. Вам требуется выполнять запросы двух типов:
- Формат запроса «0 i val». В ответ на запрос нужно выполнить присвоение: ai = val.
- Формат запроса «1 l r k». В ответ на запрос нужно вывести максимальную сумму не более чем k непересекающихся подотрезков последовательности al, al + 1, ..., ar. Формально, вам нужно выбрать не более чем k пар целых чисел (x1, y1), (x2, y2), ..., (xt, yt) (l ≤ x1 ≤ y1 < x2 ≤ y2 < ... < xt ≤ yt ≤ r; t ≤ k) таких, чтобы сумма ax1 + ax1 + 1 + ... + ay1 + ax2 + ax2 + 1 + ... + ay2 + ... + axt + axt + 1 + ... + ayt была как можно больше. Обратите внимание, что требуется выбрать не более чем k подотрезков. В частности, можно выбрать 0 подотрезков. В таком случае описанная сумма считается равной нулю.
Выходные данные
Для каждого запроса на подсчет максимальной суммы не более чем k непересекающихся подотрезков выведите ответ — максимальную сумму. Ответы на запросы выводите в порядке следования запросов во входных данных.
Примечание
В первом запросе первого примера можно выбрать единственную пару (1, 9). Таким образом, описанная сумма будет равна 17.
Взгляните на второй запрос первого примера. Как выбрать два подотрезка? (1, 3) и (7, 9)? Нет, конечно: сумма (1, 3) и (7, 9) равняется 20, в то время как при оптимальном выборе (1, 7) и (9, 9) сумма равняется 25.
Ответ на третий запрос равняется 0, мы предпочитаем ничего не выбирать, если на данном интервале все числа отрицательные.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
9 -8 9 -1 -1 -1 9 -8 9
3
1 1 9 1
1 1 9 2
1 4 6 3
|
17
25
0
|
|
2
|
15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
15
1 3 9 2
1 6 12 1
0 6 5
0 10 -7
1 4 9 1
1 7 9 1
0 10 -3
1 4 10 2
1 3 13 2
1 4 11 2
0 15 -9
0 13 -9
0 11 -10
1 5 14 2
1 6 12 1
|
14
11
15
0
15
26
18
23
8
|