题目描述

Misha 通过了驾照理论考试，接下来要参加实际驾驶考试。但他不会在冰面上驾驶。

考试场地是一条线形道路，有 $n$ 个交叉口。第 $i$ 个交叉口和第 $i+1$ 个交叉口之间有一条长度为 $d_i$ 的道路。初始时，第 $i$ 个交叉口有 $w_i$ 单位冰。

考官会选择一个连续区间 $[l,r]$ 作为考试线路，包含编号 $l$ 到 $r$ 的交叉口以及相邻道路。为了让线路成为环形，他们还会在交叉口 $l$ 和 $r$ 之间加一条长度为 $x$ 的临时道路。

为了阻止 Misha 通过考试，所有道路都必须被冰覆盖。一单位冰可以覆盖一单位道路；一条道路所需的冰只能从它两端的交叉口搬来；每个交叉口搬到相邻两条道路上的冰总量不能超过该交叉口现有冰量。

现在需要支持三类操作：修改某个交叉口冰量、修改某条道路长度、询问某个区间加临时道路后，至少还需要往交叉口补充多少单位冰，才能覆盖整个环形线路。

输入格式

第一行包含两个整数 $n,q$，表示交叉口数量和询问数量，满足 $2\le n\le 2\cdot 10^5$，$1\le q\le 2\cdot 10^5$。

第二行包含 $n$ 个整数 $w_i$，表示各交叉口初始冰量，$1\le w_i\le 10^9$。

第三行包含 $n-1$ 个整数 $d_i$，表示相邻交叉口之间的道路长度，$1\le d_i\le 10^9$。

接下来 $q$ 行，每行表示一个操作：

• 1 p x：令 $w_p:=x$；
• 2 p x：令 $d_p:=x$；
• 3 l r x：询问区间 $[l,r]$ 加上一条长度为 $x$ 的临时道路后，最少需要额外添加多少冰。

保证至少有一个三类询问。

输出格式

对每个三类询问，输出一个整数，表示最少需要额外添加的冰量。

样例

输入
6 7
5 9 5 1 9 5
4 8 10 4 5
3 1 6 12
3 4 6 5
2 4 1
1 6 3
3 4 6 5
1 2 3
3 2 3 6

输出
9
0
1
6

图示说明

虚线表示闭合环的临时道路；交叉口处标出当前冰量与额外添加冰量，道路上标出从两端搬来的冰量。