Description

Although there are many pictures, luckily, Wenwen has already arranged them into a line, numbered from left to right as $1 \sim n$. The three pictures Wenwen chooses should form a subsequence of length $\bf 3$. (Let the chosen photo indices be $i, j, k$, then it must satisfy $i < j < k$.)

In addition, Wenwen assigns each photo an attractiveness $A_i$ and a size $B_i$.

Because an overly large newspaper layout will reduce readers' interest, after choosing two photos $i, k$, it is required that the smallest $B_j$ must be chosen.

Formally, define $\psi(i,k) = A_i + A_k - \min(B_j)$, where it needs to satisfy $i < j < k$.

After figuring out how to compute the value of the photos, Wenwen will give you a total of $m$ operations, which can be divided into the following three types:

• $\colorbox{f0f0f0}{\verb!1 x y!}$: The attractiveness of a photo changes. Wenwen modifies $A_x$ to $y$.

• $\colorbox{f0f0f0}{\verb!2 x y!}$: The size of a photo changes. Wenwen modifies $B_x$ to $y$.

• $\colorbox{f0f0f0}{\verb!3 l r!}$: Wenwen plans to use the pictures from the $l$-th to the $r$-th in the material library. You need to tell her the maximum value of $\psi(x,y)$ ( $l \le x \le x+1 < y \le r$ ).

Input Format

The first line contains two integers $n, m$, representing the number of photos and the number of operations.

The second line contains $n$ integers, representing the sequence $A$, describing the attractiveness of each photo.

The third line contains $n$ integers, representing the sequence $B$, describing the size of each photo.

The next $m$ lines each describe an operation, in the format described above.

Output Format

For each type 3 operation, output one line with one integer, representing the answer.

6 6
1 4 2 3 5 6
5 3 4 1 6 7
3 2 5
3 1 6
1 2 3
3 1 6
2 6 1
3 1 6

8
9
8
8

Hint

Constraints and conventions

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,m} & \textbf{Special property} & \textbf{Score}\cr\hline 1 & 1\le n,m\le 300 & \text{None} & 10\cr\hline 2 & 1\le n,m\le 5\times 10^3 & \text{None} & 20\cr\hline 3 & 1\le n,m\le 5\times 10^5 & \text{Only operation 3} & 20\cr\hline 4 & 1\le n,m\le 10^5 & \text{None} & 20\cr\hline 5 & \text{No special restrictions} & \text{None} & 30\cr\hline \end{array}$$

• For $100\%$ of the testdata:

  $1 \le n,m \le 5 \times 10^5$.

  $1 \leq A_i,B_i,y \leq 10^8$, $1 \le x \le n$, $1 \le l \le r \le n$.

  It is guaranteed that $r-l+1 \geq 3$, i.e., the length of the queried interval is at least $3$.

Translated by ChatGPT 5