F. Два подотрезка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

В третьей строке заданы $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$).

В четвертой строке задано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$).

В следующих $$$q$$$ строках заданы запросы: по одному в строке. Каждый запрос имеет один из трех типов:

  • «$$$1$$$ $$$p$$$ $$$x$$$» ($$$1 \le p \le n$$$; $$$-10^9 \le x \le 10^9$$$);
  • «$$$2$$$ $$$p$$$ $$$x$$$» ($$$1 \le p \le n$$$; $$$-10^9 \le x \le 10^9$$$);
  • «$$$3$$$ $$$l$$$ $$$r$$$» ($$$1 \le l < r \le n$$$).

Гарантируется, что есть хотя бы один запрос третьего типа.

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

Для каждого запроса третьего типа выведите максимально возможную суммарную стоимость двух непустых непересекающихся подотрезков у отрезка $$$[l, r]$$$.

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