311002: CF1919F2. Wine Factory (Hard Version)

F2. Wine Factory (Hard Version)time limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

This is the hard version of the problem. The only difference between the two versions is the constraint on $c_i$ and $z$. You can make hacks only if both versions of the problem are solved.

There are three arrays $a$, $b$ and $c$. $a$ and $b$ have length $n$ and $c$ has length $n-1$. Let $W(a,b,c)$ denote the liters of wine created from the following process.

Create $n$ water towers. The $i$-th water tower initially has $a_i$ liters of water and has a wizard with power $b_i$ in front of it. Furthermore, for each $1 \le i \le n - 1$, there is a valve connecting water tower $i$ to $i + 1$ with capacity $c_i$.

For each $i$ from $1$ to $n$ in this order, the following happens:

1. The wizard in front of water tower $i$ removes at most $b_i$ liters of water from the tower and turns the removed water into wine.
2. If $i \neq n$, at most $c_i$ liters of the remaining water left in water tower $i$ flows through the valve into water tower $i + 1$.

There are $q$ updates. In each update, you will be given integers $p$, $x$, $y$ and $z$ and you will update $a_p := x$, $b_p := y$ and $c_p := z$. After each update, find the value of $W(a,b,c)$. Note that previous updates to arrays $a$, $b$ and $c$ persist throughout future updates.

Input

The first line contains two integers $n$ and $q$ ($2 \le n \le 5\cdot 10^5$, $1 \le q \le 5\cdot 10^5$) — the number of water towers and the number of updates.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the number of liters of water in water tower $i$.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$) — the power of the wizard in front of water tower $i$.

The fourth line contains $n - 1$ integers $c_1, c_2, \ldots, c_{n - 1}$ ($0 \le c_i \color{red}{\le} 10^{18}$) — the capacity of the pipe connecting water tower $i$ to $i + 1$.

Each of the next $q$ lines contains four integers $p$, $x$, $y$ and $z$ ($1 \le p \le n$, $0 \le x, y \le 10^9$, $0 \le z \color{red}{\le} 10^{18}$) — the updates done to arrays $a$, $b$ and $c$.

Note that $c_n$ does not exist, so the value of $z$ does not matter when $p = n$.

Output

Print $q$ lines, each line containing a single integer representing $W(a, b, c)$ after each update.

ExamplesInput

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

Output

11
8
5

Input

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

Output

31
25
29
21
23

Note

The first update does not make any modifications to the arrays.

• When $i = 1$, there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
• When $i = 2$, there are $5$ liters of water in tower 2 and $4$ liters of water is turned into wine. The remaining $1$ liter of water flows into tower 3.
• When $i = 3$, there are $4$ liters of water in tower 3 and $2$ liters of water is turned into wine. Even though there are $2$ liters of water remaining, only $1$ liter of water can flow into tower 4.
• When $i = 4$, there are $4$ liters of water in tower 4. All $4$ liters of water are turned into wine.

Hence, $W(a,b,c)=1 + 4 + 2 + 4 = 11$ after the first update.

The second update modifies the arrays to $a = [3, 5, 3, 3]$, $b = [1, 1, 2, 8]$, and $c = [5, 1, 1]$.

• When $i = 1$, there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
• When $i = 2$, there are $7$ liters of water in tower 2 and $1$ liter of water is turned into wine. Even though there are $6$ liters of water remaining, only $1$ liter of water can flow to tower 3.
• When $i = 3$, there are $4$ liters of water in tower 3 and $2$ liters of water is turned into wine. Even though there are $2$ liters of water remaining, only $1$ liter of water can flow into tower 4.
• When $i = 4$, there are $4$ liters of water in tower 4. All $4$ liters of water are turned into wine.

Hence, $W(a,b,c)=1 + 1 + 2 + 4 = 8$ after the second update.

The third update modifies the arrays to $a = [3, 5, 0, 3]$, $b = [1, 1, 0, 8]$, and $c = [5, 1, 0]$.

• When $i = 1$, there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
• When $i = 2$, there are $7$ liters of water in tower 2 and $1$ liter of water is turned into wine. Even though there are $6$ liters of water remaining, only $1$ liter of water can flow to tower 3.
• When $i = 3$, there is $1$ liter of water in tower 3 and $0$ liters of water is turned into wine. Even though there is $1$ liter of water remaining, no water can flow to tower 4.
• When $i = 4$, there are $3$ liters of water in tower 4. All $3$ liters of water are turned into wine.

Hence, $W(a,b,c)=1 + 1 + 0 + 3 = 5$ after the third update.

题目大意：
这个问题是“酒厂”问题的困难版本。两个版本之间唯一的区别是对于c_i和z的约束。只有当两个版本的问题都解决时，你才能进行黑客攻击。

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

创建n个水塔。第i个水塔最初有a_i升水，前面有一个功率为b_i的巫师。此外，对于每个1≤i≤n-1，有一个容量为c_i的阀门连接水塔i和水塔i+1。

对于从1到n的每个i，按以下顺序发生:

1. 水塔i前的巫师从塔中取出最多b_i升水，将取出的水变成酒。
2. 如果i≠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≤n≤500000，1≤q≤500000)——水塔的数量和更新的数量。
第二行包含n个整数a_1，a_2，…，a_n(0≤a_i≤10^9)——水塔i中的水量升数。
第三行包含n个整数b_1，b_2，…，b_n(0≤b_i≤10^9)——水塔i前巫师的功率。
第四行包含n-1个整数c_1，c_2，…，c_n-1(0≤c_i≤10^18)——连接水塔i和水塔i+1的管道容量。
接下来的q行中的每一行都包含四个整数p、x、y和z(1≤p≤n，0≤x，y≤10^9，0≤z≤10^18)——对数组a、b和c的更新。
注意，c_n不存在，所以当p=n时，z的值无关紧要。

输出描述：
打印q行，每行包含一个表示每次更新后W(a，b，c)的整数值。题目大意： 这个问题是“酒厂”问题的困难版本。两个版本之间唯一的区别是对于c_i和z的约束。只有当两个版本的问题都解决时，你才能进行黑客攻击。 有三个数组a、b和c。a和b的长度为n，c的长度为n-1。W(a，b，c)表示从以下过程中产生的葡萄酒升数。 创建n个水塔。第i个水塔最初有a_i升水，前面有一个功率为b_i的巫师。此外，对于每个1≤i≤n-1，有一个容量为c_i的阀门连接水塔i和水塔i+1。 对于从1到n的每个i，按以下顺序发生: 1. 水塔i前的巫师从塔中取出最多b_i升水，将取出的水变成酒。 2. 如果i≠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≤n≤500000，1≤q≤500000)——水塔的数量和更新的数量。 第二行包含n个整数a_1，a_2，…，a_n(0≤a_i≤10^9)——水塔i中的水量升数。 第三行包含n个整数b_1，b_2，…，b_n(0≤b_i≤10^9)——水塔i前巫师的功率。 第四行包含n-1个整数c_1，c_2，…，c_n-1(0≤c_i≤10^18)——连接水塔i和水塔i+1的管道容量。 接下来的q行中的每一行都包含四个整数p、x、y和z(1≤p≤n，0≤x，y≤10^9，0≤z≤10^18)——对数组a、b和c的更新。 注意，c_n不存在，所以当p=n时，z的值无关紧要。 输出描述： 打印q行，每行包含一个表示每次更新后W(a，b，c)的整数值。