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]

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Range queries

Segment trees revisited

Tree algorithms

Data structures

Tree queries


Solutions:
from sys import stdin, stdout
import math
import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict, deque
import bisect

def devgraph(l, n, ok):
	l = [0] + l
	d = defaultdict(list)
	if ok:
		(a, b, q, c) = (2, n + 1, deque([1]), 1)
	else:
		(a, b, q, c) = (n, 0, deque([n]), -1)
	for i in range(a, b, c):
		while len(q) and l[q[-1]] <= l[i]:
			q.pop()
		if len(q) and l[q[-1]] > l[i]:
			d[q[-1]].append(i)
		q.append(i)
	return d

def dfs1(node, d, end):
	if node == end:
		return cost[node]
	elif node < end:
		return -1
	ans = -1
	for x in d[node]:
		if x != node and x >= end:
			z = dfs1(x, d, end)
			if z != -1:
				ans = z + cost[node]
	return ans

def dfs2(node, d, end):
	if node == end:
		return cost[node]
	elif node > end:
		return -1
	ans = -1
	for x in d[node]:
		if x != node and x <= end:
			z = dfs2(x, d, end)
			if z != -1:
				ans = z + cost[node]
	return ans

class Segmenttree:
	(st, n) = ([], 0)

	def __init__(self, n, l):
		self.st = [0] * (2 * n)
		self.n = n
		for i in range(n):
			self.st[i + n] = l[i]
		for i in range(n - 1, 0, -1):
			self.st[i] = self.st[i << 1] + self.st[i << 1 | 1]

	def update(self, p, val):
		self.st[p + self.n] = val
		p += self.n
		while p > 1:
			self.st[p >> 1] = self.st[p] + self.st[p ^ 1]
			p >>= 1

	def query(self, l, r):
		(l, r) = (l + self.n, r + self.n)
		res = 0
		while l < r:
			if l & 1:
				res += self.st[l]
				l += 1
			if r & 1:
				r -= 1
				res += self.st[r]
			l >>= 1
			r >>= 1
		return res

def dfs(node, d, seg, cnt, visit):
	cnt[-1] += 1
	visit[node] = True
	seg[node][0] = cnt[-1]
	for x in d[node]:
		if visit[x] == False:
			dfs(x, d, seg, cnt, visit)
	cnt[-1] += 1
	seg[node][1] = cnt[-1]

def main():
	try:
		(n, nQ) = In()
		l = list(In())
		global cost
		cost = [0] + list(In())
		right = devgraph(l, n, 1)
		left = devgraph(l, n, 0)
		right[0] = list(right.keys())
		left[0] = list(left.keys())
		upd1 = [[0, 0] for x in range(n + 1)]
		visit = [False for x in range(n + 1)]
		dfs(0, right, upd1, [-1], visit)
		seg1 = [0] * (2 * (n + 1) + 1)
		for x in range(1, n + 1):
			co = cost[x]
			seg1[upd1[x][0]] += co
			seg1[upd1[x][1]] -= co
		upd2 = [[0, 0] for x in range(n + 1)]
		visit = [False for x in range(n + 1)]
		dfs(0, left, upd2, [-1], visit)
		seg2 = [0] * (2 * (n + 1) + 1)
		for x in range(1, n + 1):
			co = cost[x]
			seg2[upd2[x][0]] += co
			seg2[upd2[x][1]] -= co
		Sg1 = Segmenttree(len(seg1), seg1)
		Sg2 = Segmenttree(len(seg2), seg2)
		for i in range(nQ):
			(a, b, c) = In()
			if a == 2:
				if c < b and upd2[b][0] < upd2[c][0] and (upd2[b][1] > upd2[c][1]):
					(st, end) = (upd2[b][0], upd2[c][0])
					su = 0
					print(Sg2.query(st, end + 1))
				elif b < c and upd1[b][0] < upd1[c][0] and (upd1[b][1] > upd1[c][1]):
					(st, end) = (upd1[b][0], upd1[c][0])
					su = 0
					print(Sg1.query(st, end + 1))
				elif b == c:
					print(cost[b])
				else:
					print(-1)
			else:
				co = cost[b]
				Sg1.update(upd1[b][0], -co)
				Sg2.update(upd2[b][0], -co)
				Sg1.update(upd1[b][1], +co)
				Sg2.update(upd2[b][1], +co)
				cost[b] = c
				co = cost[b]
				Sg1.update(upd1[b][0], +co)
				Sg2.update(upd2[b][0], +co)
				Sg1.update(upd1[b][1], -co)
				Sg2.update(upd2[b][1], -co)
	except:
		pass

def add(a, b, c):
	res = a + b
	if res >= c:
		return res - c
	else:
		return res

def mod(a, b, c):
	res = a * b
	if res >= c:
		return res % c
	else:
		return res

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	w = a // gcd(a, b)
	return w * b

def expo(a, b):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(a, b, m):
	(x, y) = (1,)
	while b > 0:
		if b & 1:
			x = mod(x, y, m)
		y = mod(y, y, m)
		b >>= 1
	return x

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return map(int, stdin.readline().split())

def I():
	return int(stdin.readline())
P = 1000000007
main()


N = 2 * 10 ** 5 + 10
MAX = 10 ** 18
height = [MAX] * N
value = [0] * N
lft_high = [0] * N
rgt_high = [0] * N
aux_lft = [0] * N
aux_rgt = [0] * N
(n, q) = (0, 0)

class FenwickTree:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def update(self, x, d):
		while x <= self.n:
			self.bit[x] += d
			x += x & -x

	def query(self, x):
		res = 0
		while x > 0:
			res += self.bit[x]
			x -= x & -x
		return res

	def range_query(self, l, r):
		return self.query(r) - self.query(l - 1)
t1 = FenwickTree(N)
t2 = FenwickTree(N)
t3 = FenwickTree(N)

def precompute_left():
	stack = [0]
	for i in range(1, n + 1):
		while height[stack[-1]] < height[i]:
			stack.pop()
		lft_high[i] = stack[-1]
		aux_lft[stack[-1]] -= value[i]
		stack.append(i)

def precompute_right():
	stack = [n + 1]
	for i in range(n, 0, -1):
		while height[stack[-1]] < height[i]:
			stack.pop()
		rgt_high[i] = stack[-1]
		aux_rgt[stack[-1]] -= value[i]
		stack.append(i)

def update(b, k):
	diff = k - value[b]
	t1.update(b, diff)
	if lft_high[b] > 0:
		t2.update(lft_high[b], -diff)
	if rgt_high[b] > 0:
		t3.update(rgt_high[b], -diff)
	value[b] = k
	aux_lft[lft_high[b]] -= diff
	aux_rgt[rgt_high[b]] -= diff

def query_left(x, y):
	if lft_high[x] >= y:
		return -1
	ans = t1.range_query(y, x) + t2.range_query(y, x)
	return ans - aux_lft[x]

def query_right(x, y):
	if rgt_high[x] <= y:
		return -1
	ans = t1.range_query(x, y) + t3.range_query(x, y)
	return ans - aux_rgt[x]

def query(x, y):
	if x == y:
		return value[x]
	elif x > y:
		return query_left(x, y)
	else:
		return query_right(x, y)
(n, q) = map(int, input().split())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for i in range(n):
	height[i + 1] = h[i]
	value[i + 1] = a[i]
precompute_left()
precompute_right()
for i in range(1, N):
	t1.update(i, value[i])
	t2.update(i, aux_lft[i])
	t3.update(i, aux_rgt[i])
for i in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		update(x, y)
	else:
		print(query(x, y))


(n, q) = map(int, input('').split())
h = list(map(int, input('').split()))
a = list(map(int, input('').split()))

def solve1():
	(right_sum, left_sum) = ([0] * n, [0] * n)
	(right, left) = ([n] * n, [-1] * n)
	tree1 = [0] * (2 * n)
	tree2 = [0] * (2 * n)
	B1 = [0] * n
	B2 = [0] * n
	taste = a[:]

	def update1(p, value):
		tree1[p + n] = value
		p = p + n
		i = p
		while i > 1:
			tree1[i >> 1] = tree1[i] + tree1[i ^ 1]
			i >>= 1

	def query1(l, r):
		res = 0
		l += n
		r += n
		while l < r:
			if l & 1:
				res += tree1[l]
				l += 1
			if r & 1:
				r -= 1
				res += tree1[r]
			l >>= 1
			r >>= 1
		return res

	def update2(p, value):
		tree2[p + n] = value
		p = p + n
		i = p
		while i > 1:
			tree2[i >> 1] = tree2[i] + tree2[i ^ 1]
			i >>= 1

	def query2(l, r):
		res = 0
		l += n
		r += n
		while l < r:
			if l & 1:
				res += tree2[l]
				l += 1
			if r & 1:
				r -= 1
				res += tree2[r]
			l >>= 1
			r >>= 1
		return res
	great = dict()
	stack1 = []
	for i in range(0, n):
		great[i] = [-1, n]
		left_sum[i] = a[i]
		while stack1 and h[stack1[-1]] <= h[i]:
			great[stack1[-1]] = [-1, i]
			stack1.pop()
		if stack1:
			left_sum[i] += left_sum[stack1[-1]]
		stack1.append(i)
	stack1 = []
	for i in range(n - 1, -1, -1):
		right_sum[i] = a[i]
		while stack1 and h[stack1[-1]] <= h[i]:
			great[stack1[-1]][0] = i
			stack1.pop()
		if stack1:
			right_sum[i] += right_sum[stack1[-1]]
		stack1.append(i)
	stack1 = []
	for i in range(n - 1, -1, -1):
		while stack1 and h[stack1[-1]] < h[i]:
			stack1.pop()
		if stack1:
			right[i] = stack1[-1]
		stack1.append(i)
	stack1 = []
	for i in range(0, n):
		while stack1 and h[stack1[-1]] < h[i]:
			stack1.pop()
		if stack1:
			left[i] = stack1[-1]
		stack1.append(i)
	for i in range(q):
		(x, y, z) = map(int, input('').split())
		if x == 1:
			diff = z - a[y - 1]
			a[y - 1] = z
			y -= 1
			prev = great[y]
			B1[y] += diff
			B2[y] += diff
			if prev[1] != n:
				B1[prev[1]] -= diff
				update1(prev[1], B1[prev[1]])
			if prev[0] != -1:
				B2[prev[0]] -= diff
				update2(prev[0], B2[prev[0]])
			update1(y, B1[y])
			update2(y, B2[y])
		else:
			y -= 1
			z -= 1
			if y == z:
				print(a[y])
			elif h[z] >= h[y]:
				print(-1)
			elif abs(y - z) == 1:
				print(a[y] + a[z])
			elif z < y:
				diff1 = query2(y, n)
				diff2 = query2(z, n)
				if z <= left[y]:
					print(-1)
				else:
					print(right_sum[z] + diff2 - diff1 - right_sum[y] + a[y])
			else:
				diff1 = query1(0, y + 1)
				diff2 = query1(0, z + 1)
				if z >= right[y]:
					print(-1)
				else:
					print(left_sum[z] + diff2 - diff1 - left_sum[y] + a[y])
solve1()


from sys import stdin, stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007

def getsum(tree, index):
	res = 0
	index = index + 1
	while index > 0:
		res += tree[index]
		index -= index & -index
	return res

def update(tree, ind, n, val):
	ind += 1
	while ind <= n:
		tree[ind] += val
		ind += ind & -ind

def makeFenwickTree(arr):
	tree = [0] * (len(arr) + 1)
	for i in range(len(arr)):
		update(tree, i, len(arr), arr[i])
	return tree

def getArrays(h, p, first=False):
	(prefix, postfix) = ([0] * n, [0] * n)
	stack = []
	(left, right) = ({}, {})
	for i in range(n):
		prefix[i] = p[i]
		while len(stack) and h[stack[-1]] <= h[i]:
			left[stack[-1]] = i
			prefix[i] -= p[stack[-1]]
			stack.pop()
		stack.append(i)
	stack = []
	for i in range(n)[::-1]:
		postfix[i] = p[i]
		while len(stack) and h[stack[-1]] <= h[i]:
			right[stack[-1]] = i
			postfix[i] -= p[stack[-1]]
			stack.pop()
		stack.append(i)
	if first:
		return [prefix, postfix, left, right]
	else:
		return [prefix, postfix]
(n, q) = iia()
h = iia()
p = iia()
(prefix, postfix, left, right) = getArrays(h, p, True)
preTree = makeFenwickTree(prefix)
postTree = makeFenwickTree(postfix[::-1])
for i in range(q):
	t = iia()
	if t[0] == 1:
		chg = t[2] - p[t[1] - 1]
		p[t[1] - 1] = t[2]
		update(preTree, t[1] - 1, len(prefix), chg)
		update(postTree, n - t[1], len(postfix), chg)
		if t[1] - 1 in right:
			update(postTree, n - right[t[1] - 1] - 1, len(postfix), -chg)
		if t[1] - 1 in left:
			update(preTree, left[t[1] - 1], len(prefix), -chg)
	else:
		(a, b) = (t[1] - 1, t[2] - 1)
		if a == b:
			print(p[a])
		elif a > b and right.get(a, float('-inf')) < b:
			asum = getsum(postTree, n - a - 1)
			bsum = getsum(postTree, n - b - 1)
			print(bsum - asum + p[a])
		elif b > a and left.get(a, float('inf')) > b:
			asum = getsum(preTree, a)
			bsum = getsum(preTree, b)
			print(bsum - asum + p[a])
		else:
			print(-1)


from collections import defaultdict
import sys
sys.setrecursionlimit(2 * 10 ** 5)

def inp_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def inp_int():
	return map(int, sys.stdin.readline().strip().split())

def dfsl(tree_left, root, epl, visl):
	for i in range(len(tree_left[root])):
		if visl[tree_left[root][i]] == False:
			visl[tree_left[root][i]] = True
			epl.append(tree_left[root][i])
			dfsl(tree_left, tree_left[root][i], epl, visl)
			epl.append(-tree_left[root][i])

def euler_left(h, n):
	stack_left = []
	for i in range(1, n + 1):
		if len(stack_left) == 0:
			stack_left.append((h[i], i))
		else:
			while len(stack_left) != 0 and stack_left[-1][0] <= h[i]:
				stack_left.pop()
			if len(stack_left) != 0:
				tree_left[i].append(stack_left[-1][1])
				tree_left[stack_left[-1][1]].append(i)
			stack_left.append((h[i], i))
	visl = [False] * (n + 1)
	for i in range(1, n + 1):
		if visl[i] == False:
			epl.append(i)
			visl[i] = True
			dfsl(tree_left, i, epl, visl)
			epl.append(-i)
	epl.insert(0, -1)
	for i in range(1, len(epl)):
		if epl[i] > 0:
			entry_left[epl[i]] = i
			update_left(i, tasty[epl[i]])
		else:
			exit_left[-epl[i]] = i
			update_left(i, -tasty[-epl[i]])

def euler_right(h, n):
	tree_right = defaultdict(list)
	stack_right = []
	for i in range(n, 0, -1):
		if len(stack_right) == 0:
			stack_right.append((h[i], i))
		else:
			while len(stack_right) != 0 and stack_right[-1][0] <= h[i]:
				stack_right.pop()
			if len(stack_right) != 0:
				tree_right[i].append(stack_right[-1][1])
				tree_right[stack_right[-1][1]].append(i)
			stack_right.append((h[i], i))
	visr = [False] * (n + 1)
	for i in range(n, 0, -1):
		if visr[i] == False:
			epr.append(i)
			visr[i] = True
			dfsl(tree_right, i, epr, visr)
			epr.append(-i)
	epr.insert(0, -1)
	for i in range(1, len(epr)):
		if epr[i] > 0:
			entry_right[epr[i]] = i
			update_right(i, tasty[epr[i]])
		else:
			exit_right[-epr[i]] = i
			update_right(i, -tasty[-epr[i]])

def update_left(pos, val):
	while pos <= 2 * n:
		fenwick_left[pos] = fenwick_left[pos] + val
		pos = pos + (pos & -pos)

def sum_left(pos):
	ans = 0
	while pos > 0:
		ans = ans + fenwick_left[pos]
		pos = pos - (pos & -pos)
	return ans

def update_right(pos, val):
	while pos <= 2 * n:
		fenwick_right[pos] = fenwick_right[pos] + val
		pos = pos + (pos & -pos)

def sum_right(pos):
	ans = 0
	while pos > 0:
		ans = ans + fenwick_right[pos]
		pos = pos - (pos & -pos)
	return ans
epl = []
epr = []
tree_left = defaultdict(list)
tree_right = defaultdict(list)
(n, q) = inp_int()
h = inp_list()
tasty = inp_list()
entry_left = [0] * (n + 1)
exit_left = [0] * (n + 1)
entry_right = [0] * (n + 1)
exit_right = [0] * (n + 1)
fenwick_left = [0] * (2 * n + 5)
fenwick_right = [0] * (2 * n + 5)
h.insert(0, 0)
tasty.insert(0, 0)
euler_left(h, n)
euler_right(h, n)
for _ in range(q):
	inp = inp_list()
	op = inp[0]
	so = inp[1]
	des = inp[2]
	if op == 1:
		update_left(entry_left[so], des - tasty[so])
		update_left(exit_left[so], -(des - tasty[so]))
		update_right(entry_right[so], des - tasty[so])
		update_right(exit_right[so], -(des - tasty[so]))
		tasty[so] = des
	if op == 2:
		res = -1
		if so == des:
			sys.stdout.write(str(tasty[so]))
			print()
		else:
			if so < des and entry_left[so] < entry_left[des] and (exit_left[so] > exit_left[des]):
				res = sum_left(entry_left[des]) - sum_left(entry_left[so] - 1)
			elif so > des and entry_right[so] < entry_right[des] and (exit_right[so] > exit_right[des]):
				res = sum_right(entry_right[des]) - sum_right(entry_right[so] - 1)
			sys.stdout.write(str(res))
			print()


def update_tree(i, n, a, Tree):
	while i < n:
		Tree[i] += a
		i |= i + 1

def get_sum_tree(i, Tree):
	sum1 = 0
	while i >= 0:
		sum1 += Tree[i]
		i &= i + 1
		i -= 1
	return sum1

def get_cost(l, r):
	if h[l] <= h[r]:
		return -1
	elif right_arr[l] <= r:
		return -1
	else:
		if flag:
			y = cost[l]
			total = get_sum_tree(r, left_tree) - get_sum_tree(l, left_tree) + y
		else:
			total = sum_left_arr[r] - sum_left_arr[l] + cost[l]
		return total

def rev_get_cost(l, r):
	if h[l] <= h[r]:
		return -1
	elif left_arr[l] >= r:
		return -1
	else:
		if flag:
			y = cost[l]
			total = get_sum_tree(r, right_tree) - get_sum_tree(l, right_tree) + y
		else:
			total = sum_right_arr[l] - sum_right_arr[r] + cost[r]
		return total
(n, q) = map(int, input().split())
h = list(map(int, input().split()))
cost = list(map(int, input().split()))
stack = []
left_arr = [-1] * n
sum_left_arr = [0] * n
s_len = 0
for i in range(n):
	while s_len > 0:
		if h[i] >= h[stack[-1]]:
			if left_arr[i] == -1 and h[i] == h[stack[-1]]:
				left_arr[i] = stack[-1]
			stack.pop(-1)
			s_len -= 1
		else:
			if left_arr[i] == -1:
				left_arr[i] = stack[-1]
			sum_left_arr[i] = sum_left_arr[stack[-1]] + cost[i]
			stack.append(i)
			s_len += 1
			break
	if s_len == 0:
		sum_left_arr[i] = cost[i]
		stack.append(i)
		s_len += 1
left_tree = [0] * 1000000
update_tree(0, n, sum_left_arr[0], left_tree)
for i in range(1, n):
	update_tree(i, n, sum_left_arr[i] - sum_left_arr[i - 1], left_tree)
stack = []
right_arr = [n] * n
sum_right_arr = [0] * n
s_len = 0
for i in range(n - 1, -1, -1):
	while s_len > 0:
		if h[stack[-1]] <= h[i]:
			if right_arr[i] == n and h[i] == h[stack[-1]]:
				right_arr[i] = stack[-1]
			stack.pop(-1)
			s_len -= 1
		else:
			if right_arr[i] == n:
				right_arr[i] = stack[-1]
			sum_right_arr[i] = sum_right_arr[stack[-1]] + cost[i]
			stack.append(i)
			s_len += 1
			break
	if s_len == 0:
		sum_right_arr[i] = cost[i]
		stack.append(i)
		s_len += 1
right_tree = [0] * 1000000
update_tree(0, n, sum_right_arr[0], right_tree)
for i in range(1, n):
	update_tree(i, n, sum_right_arr[i] - sum_right_arr[i - 1], right_tree)
flag = 1
for q1 in range(q):
	(type, l, r) = map(int, input().split())
	if type == 2:
		if r == l:
			print(cost[l - 1])
		elif r > l:
			print(get_cost(l - 1, r - 1))
		else:
			print(rev_get_cost(l - 1, r - 1))
	else:
		flag = 1
		l = l - 1
		RNeighbour = right_arr[l]
		update_tree(l, n, r - cost[l], left_tree)
		if RNeighbour != n:
			update_tree(RNeighbour, n, cost[l] - r, left_tree)
		LNeighbour = left_arr[l]
		if LNeighbour == -1:
			update_tree(0, n, -cost[l] + r, right_tree)
			update_tree(l + 1, n, -r + cost[l], right_tree)
		else:
			update_tree(LNeighbour + 1, n, -cost[l] + r, right_tree)
			update_tree(l + 1, n, -r + cost[l], right_tree)
		cost[l] = r


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')

def getsum(BIT, i):
	s = 0
	i += 1
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s

def updateBit(BIT, n, i, v):
	i += 1
	while i <= n:
		BIT[i] += v
		i += i & -i

def update(BIT, l, r, n, val):
	updateBit(BIT, n, l, val)
	updateBit(BIT, n, r + 1, -val)
(n, q) = map(int, input().split())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
l1 = [0] * n
l2 = [0] * n
l2[0] = a[0]
l1[n - 1] = a[n - 1]
stk = [0] * n
stk[0] = [h[n - 1], n - 1]
top = 0
for i in range(n - 2, -1, -1):
	if h[i] >= h[i + 1]:
		while top >= 0 and h[i] >= stk[top][0]:
			top -= 1
	if top == -1:
		l1[i] = a[i]
	else:
		l1[i] = a[i] + l1[stk[top][1]]
	top += 1
	stk[top] = [h[i], i]
stk[0] = [h[0], 0]
top = 0
for i in range(1, n):
	if h[i] >= h[i - 1]:
		while top >= 0 and h[i] >= stk[top][0]:
			top -= 1
	if top == -1:
		l2[i] = a[i]
	else:
		l2[i] = a[i] + l2[stk[top][1]]
	top += 1
	stk[top] = [h[i], i]
BIT1 = [0] * (n + 1)
BIT2 = [0] * (n + 1)
h1 = [0] * n
h2 = [0] * n
h1[0] = 0
h2[n - 1] = n - 1
stk[0] = [h[n - 1], n - 1]
top = 0
for i in range(n - 2, -1, -1):
	if h[i] > h[i + 1]:
		while top >= 0 and h[i] > stk[top][0]:
			top -= 1
	if top == -1:
		h2[i] = n - 1
	else:
		h2[i] = stk[top][1] - 1
	top += 1
	stk[top] = [h[i], i]
stk[0] = [h[0], 0]
top = 0
for i in range(1, n):
	if h[i] > h[i - 1]:
		while top >= 0 and h[i] > stk[top][0]:
			top -= 1
	if top == -1:
		h1[i] = 0
	else:
		h1[i] = stk[top][1] + 1
	top += 1
	stk[top] = [h[i], i]
for i in range(q):
	(a1, b1, c1) = map(int, input().split())
	if a1 == 2:
		if h[b1 - 1] <= h[c1 - 1] and b1 != c1:
			print(-1)
		else:
			if b1 < c1:
				if h2[b1 - 1] < c1 - 1:
					ans = -1
				else:
					ans = getsum(BIT2, c1 - 1) - getsum(BIT2, b1 - 1) + l2[c1 - 1] - l2[b1 - 1] + a[b1 - 1]
			elif h1[b1 - 1] > c1 - 1:
				ans = -1
			else:
				ans = getsum(BIT1, c1 - 1) - getsum(BIT1, b1 - 1) + l1[c1 - 1] - l1[b1 - 1] + a[b1 - 1]
			print(ans)
	else:
		val = c1 - a[b1 - 1]
		update(BIT1, h1[b1 - 1], b1 - 1, n, val)
		update(BIT2, b1 - 1, h2[b1 - 1], n, val)
		a[b1 - 1] = c1


from collections import defaultdict, deque
import sys
sys.setrecursionlimit(10 ** 6)

def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i

def construct(arr, n):
	BITTree = [0] * (n + 1)
	for i in range(n):
		updatebit(BITTree, n, i, arr[i])
	return BITTree

def addedge(u, v, d):
	d[u].append(v)

def dfs(neigh, visited, s, euler, a, entry, exit):
	visited[s] = True
	euler.append(a[s])
	entry[s] = len(euler) - 1
	for j in neigh[s]:
		if visited[j] == False:
			dfs(neigh, visited, j, euler, a, entry, exit)
	euler.append(-1 * a[s])
	exit[s] = len(euler) - 1
(n, q) = map(int, input().split())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
left = []
right = []
for i in range(n):
	left.append(-1)
	right.append(-1)
d = deque()
neigh1 = defaultdict(list)
neigh2 = defaultdict(list)
d.append((h[0], 0))
for i in range(1, n):
	next = (h[i], i)
	if len(d) != 0:
		if next[0] <= d[-1][0]:
			d.append(next)
		else:
			while len(d) != 0 and next[0] > d[-1][0]:
				temp = d.pop()
				right[temp[1]] = next[1]
				addedge(right[temp[1]], temp[1], neigh2)
	d.append(next)
d.clear()
d.append((h[-1], n - 1))
for i in range(n - 2, -1, -1):
	next = (h[i], i)
	if len(d) != 0:
		if next[0] <= d[-1][0]:
			d.append(next)
		else:
			while len(d) != 0 and next[0] > d[-1][0]:
				temp = d.pop()
				left[temp[1]] = next[1]
				addedge(left[temp[1]], temp[1], neigh1)
	d.append(next)
etour_left = []
entry_left = []
exit_left = []
etour_right = []
entry_right = []
exit_right = []
visited1 = []
visited2 = []
for i in range(n):
	visited1.append(False)
	visited2.append(False)
	entry_left.append(-1)
	exit_left.append(-1)
	entry_right.append(-1)
	exit_right.append(-1)
for i in range(n):
	if visited1[i] == False and left[i] == -1:
		dfs(neigh1, visited1, i, etour_left, a, entry_left, exit_left)
	if visited2[i] == False and right[i] == -1:
		dfs(neigh2, visited2, i, etour_right, a, entry_right, exit_right)
tree1 = construct(etour_left, len(etour_left))
tree2 = construct(etour_right, len(etour_right))
for i in range(q):
	(temp, l, r) = map(int, input().split())
	if temp == 1:
		l = l - 1
		temp = a[l]
		a[l] = r
		r = r - temp
		updatebit(tree1, len(etour_left), entry_left[l], r)
		updatebit(tree1, len(etour_left), exit_left[l], -1 * r)
		updatebit(tree2, len(etour_right), entry_right[l], r)
		updatebit(tree2, len(etour_right), exit_right[l], -1 * r)
	else:
		l = l - 1
		r = r - 1
		if l == r:
			print(a[l])
		elif l < r:
			if exit_left[r] > exit_left[l] or entry_left[r] < entry_left[l]:
				print(-1)
			else:
				p = entry_left[l]
				q = entry_left[r]
				print(getsum(tree1, q) - getsum(tree1, p - 1))
		elif exit_right[r] > exit_right[l] or entry_right[r] < entry_right[l]:
			print(-1)
		else:
			p = entry_right[l]
			q = entry_right[r]
			print(getsum(tree2, q) - getsum(tree2, p - 1))


from collections import deque, defaultdict

def getSum(l, r, segTree):
	ans = 0
	n = len(segTree) // 2
	l += n
	r += n
	while l < r:
		if l & 1:
			ans += segTree[l]
			l += 1
		if r & 1:
			r -= 1
			ans += segTree[r]
		l >>= 1
		r >>= 1
	return ans

def main():
	(N, Q) = map(int, input().split())
	h = list(map(int, input().split()))
	h.append(float('inf'))
	a = list(map(int, input().split()))
	a.append(0)
	prevL = [N] * N
	stack = deque([(float('inf'), N)])
	mastOrdL = [(N, 0)] * (N + 1)
	for i in range(N):
		isPopped = False
		while stack[-1][0] <= h[i]:
			stack.pop()
			isPopped = True
		prevL[i] = stack[-1][1]
		if isPopped:
			mastOrdL[i] = (i, 0)
		else:
			mastOrdL[i] = (mastOrdL[prevL[i]][0], mastOrdL[prevL[i]][1] + 1)
		stack.append((h[i], i))
	prevR = [N] * N
	stack.clear()
	stack.append((float('inf'), N))
	mastOrdR = [(N, 0)] * (N + 1)
	for i in range(N - 1, -1, -1):
		isPopped = False
		while stack[-1][0] <= h[i]:
			stack.pop()
			isPopped = True
		prevR[i] = stack[-1][1]
		if isPopped:
			mastOrdR[i] = (i, 0)
		else:
			mastOrdR[i] = (mastOrdR[prevR[i]][0], mastOrdR[prevR[i]][1] + 1)
		stack.append((h[i], i))
	Lval = defaultdict(lambda : [])
	Lval[mastOrdL[N][0]] = [0]
	for i in range(0, N):
		Lval[mastOrdL[i][0]].append(a[i])
	Rval = defaultdict(lambda : [])
	for i in range(N, -1, -1):
		Rval[mastOrdR[i][0]].append(a[i])
	for master in Lval:
		arr = Lval[master]
		n = len(arr)
		segTree = [0] * (2 * n)
		for i in range(n):
			segTree[n + i] = arr[i]
		for i in range(n - 1, 0, -1):
			segTree[i] = segTree[i << 1] + segTree[i << 1 | 1]
		Lval[master] = segTree
	for master in Rval:
		arr = Rval[master]
		n = len(arr)
		segTree = [0] * (2 * n)
		for i in range(n):
			segTree[n + i] = arr[i]
		for i in range(n - 1, 0, -1):
			segTree[i] = segTree[i << 1] + segTree[i << 1 | 1]
		Rval[master] = segTree
	for _ in range(Q):
		(qtype, x, y) = map(int, input().split())
		if qtype == 1:
			segTree = Lval[mastOrdL[x - 1][0]]
			n = len(segTree) // 2
			p = mastOrdL[x - 1][1]
			segTree[p + n] = y
			p += n
			i = p
			while i > 1:
				segTree[i >> 1] = segTree[i] + segTree[i ^ 1]
				i >>= 1
			segTree = Rval[mastOrdR[x - 1][0]]
			n = len(segTree) // 2
			p = mastOrdR[x - 1][1]
			segTree[p + n] = y
			p += n
			i = p
			while i > 1:
				segTree[i >> 1] = segTree[i] + segTree[i ^ 1]
				i >>= 1
		else:
			a_den = x - 1
			b_den = y - 1
			flag = False
			if a_den < b_den:
				total = 0
				while mastOrdL[b_den][0] != mastOrdL[a_den][0]:
					if h[a_den] <= h[b_den] or a_den > b_den:
						print(-1)
						flag = True
						break
					total += getSum(0, mastOrdL[b_den][1] + 1, Lval[mastOrdL[b_den][0]])
					b_den = prevL[mastOrdL[b_den][0]]
				if flag:
					continue
				if mastOrdL[b_den][1] >= mastOrdL[a_den][1]:
					total += getSum(mastOrdL[a_den][1], mastOrdL[b_den][1] + 1, Lval[mastOrdL[b_den][0]])
					print(total)
				else:
					print(-1)
			else:
				total = 0
				while mastOrdR[b_den][0] != mastOrdR[a_den][0]:
					if h[a_den] <= h[b_den] or a_den < b_den:
						print(-1)
						flag = True
						break
					total += getSum(0, mastOrdR[b_den][1] + 1, Rval[mastOrdR[b_den][0]])
					b_den = prevR[mastOrdR[b_den][0]]
				if flag:
					continue
				if mastOrdR[b_den][1] >= mastOrdR[a_den][1]:
					total += getSum(mastOrdR[a_den][1], mastOrdR[b_den][1] + 1, Rval[mastOrdR[b_den][0]])
					print(total)
				else:
					print(-1)
main()


import math

class Forward2:

	def __init__(self, a_l, h_l):
		self.a_l = a_l
		self.h_l = h_l
		self.compute()

	def range_query(self, left, right):
		segtree = self.segtree
		n = len(self.a_l)
		left += n
		right += n
		ma = -1
		while left < right:
			if left & 1:
				ma = max(ma, segtree[left])
				left += 1
			if right & 1:
				right -= 1
				ma = max(ma, segtree[right])
			left //= 2
			right //= 2
		return ma

	def compute(self):
		a_l = self.a_l
		h_l = self.h_l
		cur_sum = a_l[0]
		stack = [0]
		dp = [a_l[0] for _ in range(n)]
		segtree = [-1 for _ in range(2 * n + 1)]
		for i in range(n):
			segtree[n + i] = h_l[i]
		for i in range(n - 1, 0, -1):
			segtree[i] = max(segtree[2 * i], segtree[2 * i + 1])
		for i in range(1, n):
			while len(stack) > 0 and h_l[i] >= h_l[stack[-1]]:
				cur_sum -= a_l[stack[-1]]
				del stack[-1]
			cur_sum += a_l[i]
			dp[i] = cur_sum
			stack.append(i)
		self.dp = dp
		self.segtree = segtree

	def cal(self, a, b):
		a -= 1
		b -= 1
		dp = self.dp
		a_l = self.a_l
		h_l = self.h_l
		if h_l[a] > self.range_query(a + 1, b):
			return dp[b] - dp[a] + a_l[a]
		return -1

class Forward:

	def __init__(self, a_l, h_l):
		self.a_l = a_l
		self.h_l = h_l
		self.compute()

	def range_query(self, left, right):
		segtree = self.segtree
		n = len(self.a_l)
		left += n
		right += n
		ma = -1
		while left < right:
			if left & 1:
				ma = max(ma, segtree[left])
				left += 1
			if right & 1:
				right -= 1
				ma = max(ma, segtree[right])
			left //= 2
			right //= 2
		return ma

	def compute(self):
		a_l = self.a_l
		h_l = self.h_l
		stack = [0]
		jump_cld = {}
		jump_par = {}
		par_map = {1 + (1 & -1): [1]}
		dp = [0 for _ in range(n)]
		segtree = [-1 for _ in range(2 * n + 1)]
		for i in range(n):
			segtree[n + i] = h_l[i]
		for i in range(n - 1, 0, -1):
			segtree[i] = max(segtree[2 * i], segtree[2 * i + 1])
		for i in range(1, n):
			while len(stack) > 0 and h_l[i] >= h_l[stack[-1]]:
				del stack[-1]
			stack.append(i)
			ti = len(stack)
			par_i = ti - (ti & -ti) - 1
			if stack[par_i] != i:
				jump_par[i] = stack[par_i]
			cld_i = ti + (ti & -ti)
			if cld_i in par_map:
				if ti > par_map[cld_i][-1]:
					par_map[cld_i].append(ti)
			else:
				par_map[cld_i] = [ti]
			if ti in par_map:
				for v in par_map[ti]:
					v -= 1
					v = stack[v]
					if v in jump_cld:
						jump_cld[v].append(i)
					else:
						jump_cld[v] = [i]
		self.dp = dp
		self.jump_cld = jump_cld
		self.jump_par = jump_par
		self.segtree = segtree
		for i in range(n):
			self.recur(i, a_l[i])

	def recur(self, i, v):
		jump_cld = self.jump_cld
		dp = self.dp
		dp[i] += v
		if i in jump_cld:
			for cld_i in jump_cld[i]:
				self.recur(cld_i, v)

	def update(self, i, v):
		a_l = self.a_l
		i -= 1
		diff = v - a_l[i]
		self.recur(i, diff)
		a_l[i] = v

	def cal(self, a, b):
		h_l = self.h_l
		a_l = self.a_l
		jump_par = self.jump_par
		dp = self.dp
		a -= 1
		b -= 1
		h_l = self.h_l
		if h_l[a] <= self.range_query(a + 1, b):
			return -1
		total_b = 0
		par_i = b
		while True:
			total_b += dp[par_i]
			if par_i in jump_par:
				par_i = jump_par[par_i]
			else:
				break
		total_a = 0
		par_i = a
		while True:
			total_a += dp[par_i]
			if par_i in jump_par:
				par_i = jump_par[par_i]
			else:
				break
		return total_b - total_a + a_l[a]
(n, q) = map(int, input().split())
h_l = list(map(int, input().split()))
a_l = list(map(int, input().split()))
qs = []
noUpdate = True
for _ in range(q):
	(typ, a, b) = map(int, input().split())
	qs.append([typ, a, b])
	if typ == 1:
		noUpdate = False
if noUpdate:
	forward = Forward2(a_l, h_l)
	backward = Forward2(a_l[::-1], h_l[::-1])
else:
	forward = Forward(a_l, h_l)
	backward = Forward(a_l[::-1], h_l[::-1])
for (typ, a, b) in qs:
	if typ == 1:
		forward.update(a, b)
		backward.update(n + 1 - a, b)
	else:
		if a < b:
			ans = forward.cal(a, b)
		else:
			ans = backward.cal(n + 1 - a, n + 1 - b)
		print(ans)