题目描述

给定两个长度为 $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, \dots, r$ 进行操作，每次操作将 $v$ 替换为 $v + A_i$ 或 $v \times B_i$。求最终能得到的 $v$ 的最大值。 需要注意的是，输入中类型 $3$ 的查询的答案保证在 $10^{18}$ 以下。

输入格式

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

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
Q
query_1
query_2
...
query_Q

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

1 i x
2 i x
3 l r

输出格式

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

样例 1

输入

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

输出

12
7

样例 2

输入

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 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• $1 \leq Q \leq 10^5$
• 类型 $1$, $2$ 的查询中，$1 \leq i \leq N$
• 类型 $1$, $2$ 的查询中，$1 \leq x \leq 10^9$
• 类型 $3$ 的查询中，$1 \leq l \leq r \leq N$
• 类型 $3$ 的查询中，输出值在 $10^{18}$ 以下