Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is on an adventure to find the tastiest exotic spices. Everyone knows that the best spices are guarded by several ancient dragons that dwell within mountains.

The mountain range can be modeled by a polyline in the 2D $xz$ plane that passes through $N$ points $p_{1} = (1,h_{1}), p_{2} = (2, h_{2}), \ldots, p_{N} = (N, h_{N})$, in this order, where $h_{i}$ is a positive integer for each valid $i$. This polyline divides the set of points $\{(x, z): 1 ≤ x ≤ N\}$ into two regions. The "solid" part of the mountain range is the "bottom" region, i.e. the region that contains the $x$-axis (the x-axis is the line $z=0$).

A dragon's den is located at each of the $N$ points. For each valid $i$, the den at the point $p_{i}$ initially contains a pile of spices with tastiness $a_{i}$. With a technique he learned from dragons, Chef can glide from den to den, tasting all of the spices along the way. The tastiness of an entire journey is the summed up tastiness of spices over all dens visited during the journey. However, there are some restrictions:
Chef can only glide from a higher den to a strictly lower den, i.e. if he glides from a den at $p_{i}$ to a den at $p_{j}$, then $h_{i} > h_{j}$ must hold.
Chef can only glide in one direction and never look back, i.e. if he starts travelling in the direction of decreasing $x$, he must keep travelling in that direction until the end of the journey, and if he starts travelling in the direction of increasing $x$, he must keep travelling in that direction until the end of the journey too.
Chef cannot travel through solid mountain, i.e. he can only glide from a den at $p_{i}$ to a den at $p_{j}$ if the line segment connecting the points $p_{i}$ and $p_{j}$ does not intersect the "solid" part of the mountain range. However, it may touch the border of the mountain range, i.e. the polyline itself.

Note that gliding is the only way for Chef to travel between dens. It is valid for a journey to begin and end at the same den, in which case Chef tastes the spices at the den and nothing else.

See the explanation of the sample test case for a concrete example.

With that in mind, Chef needs you to process $Q$ queries. There are two types of queries:
1 b k: Chef changes his mind and decides that the tastiness of the spices in the den at the point $p_{b}$ should be changed to $k$ instead.
2 b c: Chef wants to start a journey at the den located at $p_{b}$ and end it at the den located at $p_{c}$. Find the maximum possible tastiness of such a journey or determine that no such journey exists.

------ Input ------
The first line of the input contains two space-separated integers $N$ and $Q$.
The second line contains $N$ space-separated integers $h_{1}, h_{2}, \ldots, h_{N}$.
The third line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.
Then, $Q$ lines follow. Each of these lines contains three space-separated integers describing a query in the above format.

------ Output ------
For each query of the second type, print a single line containing one integer ― the maximum tastiness of a journey or $-1$ if no valid journey exists.

------ Constraints ------
$1 ≤ N,Q ≤ 2 \cdot 10^{5}$
$1 ≤ h_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ a_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ b, c ≤ N$
$1 ≤ k ≤ 10^{9}$

------ Subtasks ------
Subtask 1 (10 points): $N, Q ≤ 1,000$

Subtask 2 (35 points): there are no queries of the first type

Subtask 3 (55 points): original constraints

----- Sample Input 1 ------
5 4

3 1 4 1 5

1 2 4 8 16

2 5 2

1 3 5

2 3 4

2 1 4
----- Sample Output 1 ------
22

13

-1
----- explanation 1 ------
Here is an illustration of the mountain range described in the first sample test case.

![fig1]

• Query 1: Starting at $p_{5}$ (height $5$), Chef can glide to $p_{3}$ (height 4) and then to $p_{2}$ (height $1$). The total tastiness of this journey is $a_{5}+a_{3}+a_{2}=16+4+2=22$.

![fig2]

• Query 2: The value of $a_{3}$ is set to $5$.
• Query 3: Chef glides from $p_{3}$ to $p_{4}$. The tastiness is $a_{3}+a_{4}=5+8=13$.
• Query 4: It is impossible to get from $p_{1}$ to $p_{4}$. Even if $h_{1} > h_{4}$, to reach $p_{4}$, Chef would need to fly either upwards or through the mountain, both of which are impossible.

![fig3]

![fig4]

见题面

见题面