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: 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. 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^{