F2. Винный завод (сложная версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между двумя версиями заключается в ограничениях на $$$c_i$$$ и $$$z$$$. Вы можете делать взломы, только если обе версии задачи решены.

Даны три массива $$$a$$$, $$$b$$$ и $$$c$$$. $$$a$$$ и $$$b$$$ имеют длину $$$n$$$, а $$$c$$$ — длину $$$n-1$$$. Обозначим за $$$W(a,b,c)$$$ количество литров вина, произведённых в результате следующего процесса.

Построим $$$n$$$ водонапорных башен. Изначально $$$i$$$-я водонапорная башня имеет $$$a_i$$$ литров воды, и перед ней стоит волшебник с силой $$$b_i$$$. Кроме того, для каждого $$$1 \le i \le n - 1$$$ существует клапан, соединяющий водонапорную башню $$$i$$$ с $$$i + 1$$$, и имеющий пропускную способность $$$c_i$$$.

Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ в этом порядке происходит следующее:

  1. Волшебник, стоящий перед водонапорной башней $$$i$$$, забирает из башни не более $$$b_i$$$ литров воды и превращает забранную воду в вино.
  2. Если $$$i \neq n$$$, то не более $$$c_i$$$ литров воды, оставшейся в водонапорной башне $$$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 \le n \le 5\cdot 10^5$$$, $$$1 \le q \le 5\cdot 10^5$$$) — количество водонапорных башен и количество обновлений.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — количество литров воды в водонапорной башне $$$i$$$.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — сила волшебника перед водонапорной башней $$$i$$$.

Четвертая строка содержит $$$n - 1$$$ целых чисел $$$c_1, c_2, \ldots, c_{n - 1}$$$ ($$$0 \le c_i \color{red}{\le} 10^{18}$$$) — пропускная способность трубы, соединяющей водонапорную башню $$$i$$$ с $$$i + 1$$$.

Каждая из следующих $$$q$$$ строк содержит четыре целых числа $$$p$$$, $$$x$$$, $$$y$$$ и $$$z$$$ ($$$1 \le p \le n$$$, $$$0 \le x, y \le 10^9$$$, $$$0 \le z \color{red}{\le} 10^{18}$$$) — обновления массивов $$$a$$$, $$$b$$$ и $$$c$$$.

Заметим, что $$$c_n$$$ не существует, поэтому величина $$$z$$$ не имеет значения при $$$p = n$$$.

Выходные данные

Выведите $$$q$$$ строк, каждая из которых содержит одно целое число, равняющееся $$$W(a, b, c)$$$ после каждого обновления.

Примеры
Входные данные
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
Выходные данные
11
8
5
Входные данные
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
Выходные данные
31
25
29
21
23
Примечание

Первое обновление не вносит никаких изменений в массивы.

  • Для $$$i = 1$$$, в башне 1 находится $$$3$$$ литра воды, и $$$1$$$ литр воды превращается в вино. Оставшиеся $$$2$$$ литра воды перетекают в башню 2.
  • Для $$$i = 2$$$, в башне 2 находится $$$5$$$ литров воды, и $$$4$$$ литра воды превращаются в вино. Оставшийся $$$1$$$ литр воды попадает в башню 3.
  • Для $$$i = 3$$$, в башне 3 находится $$$4$$$ литра воды, и $$$2$$$ литра воды превращаются в вино. Несмотря на то, что осталось $$$2$$$ литра воды, в башню 4 может попасть только $$$1$$$ литр воды.
  • Для $$$i = 4$$$, в башне 4 находится $$$4$$$ литра воды. Все $$$4$$$ литра воды превращаются в вино.

Следовательно, $$$W(a,b,c)=1 + 4 + 2 + 4 = 11$$$ после первого обновления.

Второе обновление изменяет массивы на $$$a = [3, 5, 3, 3]$$$, $$$b = [1, 1, 2, 8]$$$ и $$$c = [5, 1, 1]$$$.

  • Для $$$i = 1$$$, в башне 1 находится $$$3$$$ литра воды, и $$$1$$$ литр воды превращается в вино. Оставшиеся $$$2$$$ литра воды перетекают в башню 2.
  • Для $$$i = 2$$$, в башне 2 находится $$$7$$$ литров воды, и $$$1$$$ литр воды превращается в вино. Несмотря на то, что осталось $$$6$$$ литров воды, только $$$1$$$ литр воды может попасть в башню 3.
  • Для $$$i = 3$$$, в башне 3 находится $$$4$$$ литра воды, и $$$2$$$ литра воды превращаются в вино. Несмотря на то, что осталось $$$2$$$ литра воды, только $$$1$$$ литр воды может попасть в башню 4.
  • Для $$$i = 4$$$, в башне 4 находится $$$4$$$ литра воды. Все $$$4$$$ литра воды превращаются в вино.

Следовательно, $$$W(a,b,c)=1 + 1 + 2 + 4 = 8$$$ после второго обновления.

Третье обновление изменяет массивы на $$$a = [3, 5, 0, 3]$$$, $$$b = [1, 1, 0, 8]$$$ и $$$c = [5, 1, 0]$$$.

  • Для $$$i = 1$$$, в башне 1 находится $$$3$$$ литра воды, и $$$1$$$ литр воды превращается в вино. Оставшиеся $$$2$$$ литра воды перетекают в башню 2.
  • Для $$$i = 2$$$, в башне 2 находится $$$7$$$ литров воды, и $$$1$$$ литр воды превращается в вино. Несмотря на то, что осталось $$$6$$$ литров воды, только $$$1$$$ литр воды может попасть в башню 3.
  • Для $$$i = 3$$$ в башне 3 находится $$$1$$$ литр воды, и $$$0$$$ литров воды превращается в вино. Несмотря на то, что в башне остался $$$1$$$ литр воды, в башню 4 вода не поступает.
  • Для $$$i = 4$$$, в башне 4 находится $$$3$$$ литра воды. Все $$$3$$$ литра воды превращаются в вино.

Следовательно, $$$W(a,b,c)=1 + 1 + 0 + 3 = 5$$$ после третьего обновления.