D. Максимальная сумма k подотрезков
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество чисел в последовательности. В следующей строке записаны n целых чисел a1, a2, ..., an (|ai| ≤ 500).

В третьей строке записано целое число m (1 ≤ m ≤ 105) — количество запросов. В следующих m строках записаны запросы в формате, описанном в условии.

Для всех запросов на изменение элемента выполняются ограничения: 1 ≤ i ≤ n, |val| ≤ 500.

Для всех запросов на подсчет максимальной суммы не более чем k непересекающихся подотрезков выполняются ограничения: 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 20. Гарантируется, что количество запросов на подсчет максимальной суммы не более чем k непересекающихся подотрезков не превышает 10000.

Выходные данные

Для каждого запроса на подсчет максимальной суммы не более чем k непересекающихся подотрезков выведите ответ — максимальную сумму. Ответы на запросы выводите в порядке следования запросов во входных данных.

Примеры
Входные данные
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
Входные данные
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
Примечание

В первом запросе первого примера можно выбрать единственную пару (1, 9). Таким образом, описанная сумма будет равна 17.

Взгляните на второй запрос первого примера. Как выбрать два подотрезка? (1, 3) и (7, 9)? Нет, конечно: сумма (1, 3) и (7, 9) равняется 20, в то время как при оптимальном выборе (1, 7) и (9, 9) сумма равняется 25.

Ответ на третий запрос равняется 0, мы предпочитаем ничего не выбирать, если на данном интервале все числа отрицательные.