Background

As the well-known reporter in Gensokyo, Shameimaru Aya (Wenwen) often needs to collect photo materials for Wenwen News.

More specifically, Wenwen will collect a long sequence of pictures to provide images for a new issue of the newspaper. As a short bulletin, Wenwen will use three pictures from the material library: the first one is placed at the beginning, and the third one at the end, to attract readers' interest (after all, the beginning and the end of a newspaper are the easiest parts to be seen). The second one is to help readers understand the related content.

However, as the peerless wind god, Wenwen has collected too many photos, so she cannot process them all in a short time. As usual, Wenwen found you, who were watching from the side, hoping you could help her solve this difficulty.

Problem 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