F2. Wine Factory (Hard Version)time limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis 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:   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.  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.InputThe 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.OutputPrint q lines, each line containing a single integer representing W(a, b, c) after each update.ExamplesInput
4 33 3 3 31 4 2 85 2 14 3 8 10000000002 5 1 13 0 0 0Output
11
8
5
Input
5 510 3 8 9 23 4 10 8 16 5 9 25 4 9 11 1 1 12 7 4 84 1 1 11 8 3 3Output
31
25
29
21
23
NoteThe 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.
4 33 3 3 31 4 2 85 2 14 3 8 10000000002 5 1 13 0 0 0
11 8 5 
['data structures', 'dp', 'flows', 'greedy', 'matrices', '*2800']