F. Благоустройство
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вас назначили на очень важное дело: подготовиться к выравниванию одной особой дороги.

Дорогу можно представить как ломаную линию, начинающуюся в $$$(0, 0)$$$ и заканчивающуюся в $$$(n - 1, 0)$$$, которая состоит из $$$n$$$ вершин (включая стартовую и финишную). Координаты $$$i$$$-й вершины ломаной равны $$$(i, a_i)$$$.

«Выравнивание» дороги эквивалентно выбору некоторого отрезка из $$$(0, y_0)$$$ в $$$(n - 1, y_1)$$$ такого, что все точки ломаной находятся ниже выбранного отрезка (или на той же высоте). Значения $$$y_0$$$ и $$$y_1$$$ могут быть действительными числами.

Вы можете представить, что первоначально на дороге есть всякие ямы и ухабы, и вы начинаете насыпать на нее покрытие, пока не сделаете ее ровной. Для простоты, в точках $$$0$$$ и $$$n - 1$$$ находятся бесконечно высокие стены, а потому покрытие не вываливается наружу отрезка $$$[0, n - 1]$$$.

Цена выровненной дороги равна площади между выбранным отрезком и ломаной. Вы хотите минимизировать эту цену, а потому выровненная дорога будет необязательно горизонтальной.

Но есть одна проблема: ваша информация могла устареть. А потому вы отправили специального человека померить новые высоты. Этот человек идет из $$$0$$$ в $$$n - 1$$$ и посылает вам новые высоты $$$b_i$$$ для каждой вершины $$$i$$$ ломаной.

Так как подсчет новых высот может занять много времени, а вы не знаете, когда вас попросят отчитаться, посчитайте наименьшую цену (и соответствующие $$$y_0$$$ и $$$y_1$$$) для выравнивания дороги после получения каждого нового значения $$$b_i$$$.

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

В первой строке задано одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество вершин ломаной.

Во второй строке заданы $$$n$$$ целых чисел $$$a_0, a_1, \dots, a_{n - 1}$$$ ($$$0 \le a_i \le 10^9$$$; $$$a_0 = a_{n - 1} = 0$$$) — высоты соответствующих вершин.

В третьей строке заданы $$$n$$$ целых чисел $$$b_0, b_1, \dots, b_{n - 1}$$$ ($$$0 \le b_i \le 10^9$$$; $$$b_0 = b_{n - 1} = 0$$$) — новые высоты соответствующих вершин.

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

Выведите $$$n$$$ чисел: $$$i$$$-м числом ($$$0$$$-индексация) выведите $$$y_0 + y_1$$$ «лучшего отрезка» (т. е. сумму координат отрезка, который имеет минимальную цену), если вы уже знаете новые значения высот $$$b_0, \dots, b_i$$$.

Если существует несколько «лучших отрезков», выведите наименьшее возможное значение $$$y_0 + y_1$$$.

Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-9}$$$.

Формально, пусть ваш ответ равен $$$x$$$, а ответ жюри равен $$$y$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-9}$$$.

Примеры
Входные данные
5
0 5 1 3 0
0 1 3 2 0
Выходные данные
8.000000000000 4.000000000000 6.000000000000 6.000000000000 6.000000000000
Входные данные
6
0 4 1 3 3 0
0 1 4 0 1 0
Выходные данные
7.000000000000 5.000000000000 7.500000000000 7.500000000000 6.666666666667 6.666666666667
Примечание

Первый ответ на первый пример изображен выше.

Вы можете получить второй ответ, выбрав следующий «лучший отрезок»:

Вы можете достигнуть третий ответ, используя следующий «лучший отрезок»:

Вы можете получить четвертый ответ следующим образом: