Problem Description

Given two sequences of positive integers $A$ and $B$ of length $N$, process $Q$ queries given in the following format in the order they are given. Each query is one of the following three types:

• Type $1$: Given in the format 1 i x. Replace $A_i$ with $x$.
• Type $2$: Given in the format 2 i x. Replace $B_i$ with $x$.
• Type $3$: Given in the format 3 l r. Solve the following problem and output the answer:
• Initially, let $v = 0$. For $i = l, l + 1, \dots, r$, perform the operation of replacing $v$ with $v + A_i$ or $v \times B_i$. Find the maximum value that can be achieved for $v$ at the end.

Note that the answer for any Type $3$ query given in the input is guaranteed to be at most $10^{18}$.

Input Format

The input is given from the 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 Format

Let the number of Type $3$ queries be $q$. Output $q$ lines. The $i$-th line should contain the answer for the $i$-th Type $3$ query.

Sample Input and Output

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

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

Notes/Hints

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$
• The value to be output for any Type $3$ query is guaranteed to be at most $10^{18}$

Sample Explanation 1

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 $.

见题面 Input 部分

见题面 Output 部分