葡萄酒工厂（困难版）

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有三个数组 $a,b,c$。其中 $a,b$ 的长度为 $n$，$c$ 的长度为 $n-1$。

建立 $n$ 个水塔。第 $i$ 个水塔初始有 $a_i$ 升水，塔前巫师最多能把其中 $b_i$ 升水转化为葡萄酒。对每个 $1\le i<n$，水塔 $i$ 与 $i+1$ 之间有容量为 $c_i$ 的单向阀门。

按 $i=1,2,\ldots,n$ 的顺序处理水塔：

1. 巫师从当前水塔取出至多 $b_i$ 升水并全部转化为葡萄酒；
2. 若 $i<n$，当前塔剩余的水中至多有 $c_i$ 升流入下一座水塔。

设整个过程得到的葡萄酒总量为 $W(a,b,c)$。

共有 $q$ 次修改。每次给出 $p,x,y,z$，令 $a_p:=x$、$b_p:=y$、$c_p:=z$。修改会保留到之后；当 $p=n$ 时 $c_n$ 不存在，$z$ 无实际意义。每次修改后输出当前的 $W(a,b,c)$。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $a_1,\ldots,a_n$。

第三行 $n$ 个整数 $b_1,\ldots,b_n$。

第四行 $n-1$ 个整数 $c_1,\ldots,c_{n-1}$。

接下来 $q$ 行，每行四个整数 $p,x,y,z$，表示一次修改。

输出格式

输出 $q$ 行，每行一个整数，表示对应修改后的葡萄酒总量。

样例输入 1

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

样例输出 1

11
8
5

样例输入 2

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

样例输出 2

31
25
29
21
23

数据范围

$2\le n\le5\times10^5$，$1\le q\le5\times10^5$，$0\le a_i,b_i,x,y\le10^9$，$0\le c_i,z\le10^{18}$，$1\le p\le n$。

每个测试点独立计分。