Photo Selection Optimization

There are n photos in a row, numbered from \(1\) to \(n\). Each photo \(i\) has an attractiveness \(A_i\) and a size \(B_i\). You need to select three photos forming a subsequence \(i, j, k\) with \(i < j < k\). However, once you choose the two boundary photos \(i\) and \(k\), the middle one must be the one with the minimum \(B\) among those with indices strictly between \(i\) and \(k\).

The value of such a triple is defined as \[ \psi(i,k)=A_i+A_k-\min_{i<j<k} B_j. \]

You will be given \(m\) operations of the following three types:

• 1 x y: Update the attractiveness of photo \(x\) to \(y\), i.e. set \(A_x=y\).
• 2 x y: Update the size of photo \(x\) to \(y\), i.e. set \(B_x=y\).
• 3 l r: Considering the photos numbered from \(l\) to \(r\), output the maximum possible value of \(\psi(i,k)\) for any valid triple \(i, j, k\) satisfying \(l \le i < j < k \le r\). You may assume that every query \(3\) is given on a range containing at least three photos.

Your task is to process all operations and answer all queries of type 3.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of photos and the number of operations.

The second line contains \(n\) integers \(A_1, A_2, \dots, A_n\), where \(A_i\) is the attractiveness of the \(i\)-th photo.

The third line contains \(n\) integers \(B_1, B_2, \dots, B_n\), where \(B_i\) is the size of the \(i\)-th photo.

Then \(m\) lines follow, each line representing an operation in one of the following formats:

• 1 x y
• 2 x y
• 3 l r

It is guaranteed that for each query of type 3, the interval \([l,r]\) contains at least three photos.

outputFormat

For each operation of type 3, output a single line containing the maximum value of \(\psi(i,k)\) in the given range.

sample

5 5
1 2 3 4 5
5 4 3 2 1
3 1 5
1 3 10
3 1 5
2 4 0
3 2 5

6
13
15