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

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

$1$ $i$ $x$

$2$ $i$ $x$

$3$ $l$ $r$

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$

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.

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

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