Score : $575$ points

问题陈述

你得到了两个正整数序列 $A$ 和 $B$，它们的长度都是 $N$。按照给定的顺序处理 $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, ..., r$，将 $v$ 替换为 $v + A_i$ 或 $v \times B_i$。找到最终可能的最大 $v$ 值。

保证给定类型 $3$ 查询的答案最多为 $10^{18}$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given sequences of positive integers $A$ and $B$ of length $N$. Process $Q$ queries given in the following forms in the order they are given. Each query is of one of the following three types.

• Type $1$: Given in the form 1 i x. Replace $A_i$ with $x$.
• Type $2$: Given in the form 2 i x. Replace $B_i$ with $x$.
• Type $3$: Given in the form 3 l r. Solve the following problem and print the answer.
  • Initially, set $v = 0$. For $i = l, l+1, ..., r$ in this order, replace $v$ with either $v + A_i$ or $v \times B_i$. Find the maximum possible value of $v$ at the end.

It is guaranteed that the answers to the given type $3$ queries are at most $10^{18}$.

Constraints

• $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$
• For type $1$ and $2$ queries, $1 \leq i \leq N$.
• For type $1$ and $2$ queries, $1 \leq x \leq 10^9$.
• For type $3$ queries, $1 \leq l \leq r \leq N$.
• For type $3$ queries, the value to be printed is at most $10^{18}$.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

$B_1$ $B_2$ $\cdots$ $B_N$

$Q$

$query_1$

$query_2$

$\vdots$

$query_Q$

Here, $query_i$ is the $i$-th query, given in one of the following formats:

$1$ $i$ $x$

$2$ $i$ $x$

$3$ $l$ $r$

Output

Let $q$ be the number of type $3$ queries. Print $q$ lines. The $i$-th line should contain the answer to the $i$-th type $3$ query.

Sample Input 1

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

Sample Output 1

12
7

For the first query, the answer is $((0 + A_1) \times B_2) \times B_3 = 12$. For the third query, the answer is $((0 + A_1) + A_2) + A_3 = 7$.

Sample Input 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

Sample Output 2

46080
69840
27648
1728