Description

尽管图片非常多，但幸运的是，文文已经将它们排成了一列，从左到右分别编号为 $1 \sim n$，文文选取的三张图片，应该是一个长度为 $\bf 3$ 的子序列。（不妨设选取的照片的序号为 $i,j,k$ ，则必须要有 $i<j<k$ ）。

此外，文文给每张照片定了一个吸引度 $A_i$ 与大小 $B_i$ 。

因为报纸版面太大会降低读者的兴趣，于是选定两张照片 $i,k$ 后，规定必须选择最小的 $B_j$。

形式化地说，规定 $\psi(i,k) = A_i + A_k - \min(B_j)$，其中需要满足 $i < j < k$。

摸清了照片价值的计算，文文会告诉你共 $m$ 个操作，可以分为以下三种：

• $\colorbox{f0f0f0}{\verb!1 x y!}$ ：照片的吸引度发生变化。文文要将 $A_x$ 修改为 $y$ 。

• $\colorbox{f0f0f0}{\verb!2 x y!}$ ：照片的大小发生变化。文文要将 $B_x$ 修改为 $y$ 。

• $\colorbox{f0f0f0}{\verb!3 l r!}$ ：文文打算利用素材库的第 $l$ 到第 $r$ 张中的图片，你要告诉她 $\psi(x,y)$ 的最大值（ $l\le x\le x+1<y \le r$ ）。

Input Format

第一行两个整数 $n,m$，分别表示照片数量和操作次数。

第二行 $n$ 个整数，表示序列 $A$，描述每张照片的吸引度。

第三行 $n$ 个整数，表示序列 $B$，描述每张照片的大小。

接下来 $m$ 行，每行描述一个操作，格式如上所述。

Output Format

对于每个操作三，输出一行一个整数，表示答案。

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

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,m} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & 1\le n,m\le 300 & \text{无} & 10\cr\hline 2 & 1\le n,m\le 5\times 10^3 & \text{无} & 20\cr\hline 3 & 1\le n,m\le 5\times 10^5 & \text{仅有操作 3} & 20\cr\hline 4 & 1\le n,m\le 10^5 & \text{无} & 20\cr\hline 5 & \text{无特殊限制} & \text{无} & 30\cr\hline \end{array}$$

• 对于 $100\%$ 的数据：

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

  保证 $r-l+1 \geq 3$，即询问的区间长度大于等于 $3$