加法和乘法查询

题目描述

给定长度为 $N$ 的正整数序列 $A$ 和 $B$。按给定顺序依次处理 $Q$ 个查询。每个查询是以下三种类型之一。

类型 1：以 1 i x 的形式给出。将 $A_i$ 替换为 $x$。

类型 2：以 2 i x 的形式给出。将 $B_i$ 替换为 $x$。

类型 3：以 3 l r 的形式给出。解决以下问题并输出答案。

初始设 $v=0$。按 $i=l,l+1,\ldots,r$ 的顺序，将 $v$ 替换为 $v+A_i$ 或 $v\times B_i$。求最终 $v$ 的最大可能值。

保证给出的类型 3 查询的答案不超过 $10^{18}$。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

其中，第 $i$ 个查询 $query_i$ 是以下格式之一：

$1$ $i$ $x$

$2$ $i$ $x$

$3$ $l$ $r$

输出格式

设 $q$ 为类型 3 查询的个数。输出 $q$ 行。第 $i$ 行输出第 $i$ 个类型 3 查询的答案。

样例

3
3 2 4
1 2 2
3
3 1 3
1 1 1
3 1 3

12
7

对于第一个查询，答案为 $((0+A_1)\times B_2)\times B_3=12$。 对于第三个查询，答案为 $((0+A_1)+A_2)+A_3=7$。

6
65 32 12 5 8 312
4 1 3 15 16 2
6
3 2 6
3 1 5
1 5 6
2 4 9
3 2 6
3 3 5

46080
69840
27648
1728

数据范围

• $1 \le N \le 10^5$
• $1 \le A_i \le 10^9$
• $1 \le B_i \le 10^9$
• $1 \le Q \le 10^5$
• 对于类型 1 和 2 的查询，$1 \le i \le N$。
• 对于类型 1 和 2 的查询，$1 \le x \le 10^9$。
• 对于类型 3 的查询，$1 \le l \le r \le N$。
• 对于类型 3 的查询，要输出的值不超过 $10^{18}$。