F1. Винный завод (простая версия)
ограничение по времени на тест
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}$$$ ($$$c_i \color{red}{=} 10^{18}$$$) — пропускная способность трубы, соединяющей водонапорную башню $$$i$$$ с $$$i + 1$$$.

Каждая из следующих $$$q$$$ строк содержит четыре целых числа $$$p$$$, $$$x$$$, $$$y$$$ и $$$z$$$ ($$$1 \le p \le n$$$, $$$0 \le x, y \le 10^9$$$, $$$z \color{red}{=} 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
1000000000000000000 1000000000000000000 1000000000000000000
4 3 8 1000000000000000000
2 5 1 1000000000000000000
3 0 0 1000000000000000000
Выходные данные
12
12
10
Входные данные
5 5
10 3 8 9 2
3 4 10 8 1
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
5 4 9 1000000000000000000
1 1 1 1000000000000000000
2 7 4 1000000000000000000
4 1 1 1000000000000000000
1 8 3 1000000000000000000
Выходные данные
34
25
29
21
27
Примечание

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

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

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

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

  • Для $$$i = 1$$$, в башне 1 находится $$$3$$$ литра воды, и $$$1$$$ литр воды превращается в вино. Оставшиеся $$$2$$$ литра воды перетекают в башню 2.
  • Для $$$i = 2$$$, в башне 2 находится $$$7$$$ литров воды, и $$$1$$$ литр воды превращается в вино. Оставшиеся $$$6$$$ литров воды попадают в башню 3.
  • Для $$$i = 3$$$, в башне 3 находится $$$9$$$ литров воды и $$$2$$$ литра воды превращается в вино. Оставшиеся $$$7$$$ литров воды попадают в башню 4.
  • Для $$$i = 4$$$, в башне 4 находится $$$10$$$ литров воды. Только $$$8$$$ литров воды превращается в вино.

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

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

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

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