F2. 葡萄酒工厂（困难版本）
每个测试的时间限制：$5$ 秒
内存限制：$512$ MB

这是问题的困难版本。两个版本之间的唯一区别是对 $c_i$ 和 $z$ 的约束。只有当问题的两个版本都解决时，你才能进行 hack。

有三个数组 $a$、$b$ 和 $c$。$a$ 和 $b$ 的长度为 $n$，$c$ 的长度为 $n-1$。令 $W(a,b,c)$ 表示通过以下过程产生的葡萄酒的升数。

创建 $n$ 个水塔。第 $i$ 个水塔最初有 $a_i$ 升水，并且在其前面有一位能力为 $b_i$ 的巫师。此外，对于每个 $1 \le i \le n-1$，有一个连接水塔 $i$ 和水塔 $i+1$ 的阀门，容量为 $c_i$。

对于每个 $i$ 从 $1$ 到 $n$，按顺序发生以下情况：

• 水塔 $i$ 前面的巫师从塔中移出最多 $b_i$ 升水，并将移出的水转化为葡萄酒。
• 如果 $i \neq n$，水塔 $i$ 中剩余的水中最多有 $c_i$ 升通过阀门流入水塔 $i+1$。

共有 $q$ 次更新。在每次更新中，你会得到整数 $p$、$x$、$y$ 和 $z$，并更新 $a_p:=x$，$b_p:=y$ 以及 $c_p:=z$。每次更新后，求 $W(a,b,c)$ 的值。注意，之前对数组 $a$、$b$ 和 $c$ 的更新会在后续所有更新中持续生效。

输入
第一行包含两个整数 $n$ 和 $q$ $(2 \le n \le 5 \cdot 10^5$，$1 \le q \le 5 \cdot 10^5)$ — 水塔的数量和更新的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$ $(0 \le a_i \le 10^9)$ — 水塔 $i$ 中水的升数。

第三行包含 $n$ 个整数 $b_1,b_2,\dots,b_n$ $(0 \le b_i \le 10^9)$ — 水塔 $i$ 前面的巫师的能力。

第四行包含 $n-1$ 个整数 $c_1,c_2,\dots,c_{n-1}$ $(0 \le c_i \le 10^{18})$ — 连接水塔 $i$ 到水塔 $i+1$ 的管道容量。

接下来的 $q$ 行，每行包含四个整数 $p$、$x$、$y$ 和 $z$ $(1 \le p \le n$，$0 \le x,y \le 10^9$，$0 \le z \le 10^{18})$ — 对数组 $a$、$b$ 和 $c$ 的更新。

注意 $c_n$ 不存在，所以当 $p=n$ 时，$z$ 的值没有影响。

输出
输出 $q$ 行，每行一个整数，表示每次更新后的 $W(a,b,c)$。

示例
输入：

4 3
3 3 3 3
1 4 2 8
5 2 1
4 3 8 1000000000
2 5 1 1
3 0 0 0

输出：

11
8
5

输入：

5 5
10 3 8 9 2
3 4 10 8 1
6 5 9 2
5 4 9 1
1 1 1 1
2 7 4 8
4 1 1 1
1 8 3 3

输出：

31
25
29
21
23

说明
第一次更新没有对数组做任何修改。

• 当 $i=1$ 时，水塔 $1$ 中有 $3$ 升水，$1$ 升水被转化为葡萄酒。剩余的 $2$ 升水流向水塔 $2$。
• 当 $i=2$ 时，水塔 $2$ 中有 $5$ 升水，$4$ 升水被转化为葡萄酒。剩余的 $1$ 升水流向水塔 $3$。
• 当 $i=3$ 时，水塔 $3$ 中有 $4$ 升水，$2$ 升水被转化为葡萄酒。尽管剩余 $2$ 升水，只有 $1$ 升水可以流向水塔 $4$。
• 当 $i=4$ 时，水塔 $4$ 中有 $4$ 升水。所有 $4$ 升水都被转化为葡萄酒。

因此，第一次更新后 $W(a,b,c)=1+4+2+4=11$。

第二次更新将数组修改为 $a=[3,5,3,3]$，$b=[1,1,2,8]$，$c=[5,1,1]$。

• 当 $i=1$ 时，水塔 $1$ 中有 $3$ 升水，$1$ 升水被转化为葡萄酒。剩余的 $2$ 升水流向水塔 $2$。
• 当 $i=2$ 时，水塔 $2$ 中有 $7$ 升水，$1$ 升水被转化为葡萄酒。尽管剩余 $6$ 升水，只有 $1$ 升水可以流向水塔 $3$。
• 当 $i=3$ 时，水塔 $3$ 中有 $4$ 升水，$2$ 升水被转化为葡萄酒。尽管剩余 $2$ 升水，只有 $1$ 升水可以流向水塔 $4$。
• 当 $i=4$ 时，水塔 $4$ 中有 $4$ 升水。所有 $4$ 升水都被转化为葡萄酒。

因此，第二次更新后 $W(a,b,c)=1+1+2+4=8$。

第三次更新将数组修改为 $a=[3,5,0,3]$，$b=[1,1,0,8]$，$c=[5,1,0]$。

• 当 $i=1$ 时，水塔 $1$ 中有 $3$ 升水，$1$ 升水被转化为葡萄酒。剩余的 $2$ 升水流向水塔 $2$。
• 当 $i=2$ 时，水塔 $2$ 中有 $7$ 升水，$1$ 升水被转化为葡萄酒。尽管剩余 $6$ 升水，只有 $1$ 升水可以流向水塔 $3$。
• 当 $i=3$ 时，水塔 $3$ 中有 $1$ 升水，$0$ 升水被转化为葡萄酒。尽管剩余 $1$ 升水，没有水可以流向水塔 $4$。
• 当 $i=4$ 时，水塔 $4$ 中有 $3$ 升水。所有 $3$ 升水都被转化为葡萄酒。

因此，第三次更新后 $W(a,b,c)=1+1+0+3=5$。