F. 两个子数组
时间限制：3 秒
内存限制：512 MB

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$。

定义子数组 $[l, r]$ 的代价为：

若 $l = r$，则代价为 $a_l + 2 \cdot b_l$。

你需要执行三种类型的查询：

1. 更新：
   • 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$ 行，每行一个查询，格式如上。
保证至少有一个第 $3$ 类查询。

输出
对于每个第 $3$ 类查询，输出一行一个整数，表示在区间 $[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