Hello 2024 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

flows

greedy

matrices

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
F2. Wine Factory (Hard Version)

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard 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.

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.

Examples

Input

4 33 3 3 31 4 2 85 2 14 3 8 10000000002 5 1 13 0 0 0

Output

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 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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2024 10:03:18 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|