Description

Time goes back to June 7, 2017. In the afternoon, the sunlight is just right.

You, in the examination room, keep writing without stopping. Amid the rustling sounds, you fill in an answer sheet meant for your past and future selves.

Just like you have practiced countless times, you jump straight to the last big problem on this math paper. For the either-or question, you directly choose the latter. After quickly skimming the statement, your furrowed brows gradually relax.

“This is in the bag.”

You do not dare to pause for even a moment, and you move one small step closer to your dream.

Given two $n$-dimensional real vectors $\vec{a}=(a_1,a_2,\dots,a_n)$ and $\vec{b}=(b_1,b_2,\dots,b_n)$, define $n$ functions $f_1,f_2,\dots,f_n$ with domain $\mathbb{R}$:

$$f_k(x)=\sum_{i=1}^{k} \lvert a_ix+b_i\rvert \quad (k=1,2,\dots,n)$$

Now, for each $k=1,2,\dots,n$, find the minimum value of $f_k$ over $\mathbb{R}$. It can be proven that the minimum always exists.

Input Format

The first line contains an integer $n$, representing the length of the vectors and the number of functions.

The next two lines each contain $n$ integers, describing the components of vectors $\vec{a}$ and $\vec{b}$, separated by spaces.

For all input data, it holds that $1\le n\le 5\times 10^5$ and $\lvert a_i\rvert ,\lvert b_i\rvert <10^5$.

Output Format

Output $n$ lines. The $i$-th line ($i=1,2,\dots,n$) contains a real number, representing the minimum value of $f_i$ over $\mathbb{R}$.

Your output will be considered correct if the absolute error or relative error compared with the standard answer is less than $10^{-6}$.

2
1 1
1 2

0.00000
1.00000

Hint

Sample Explanation

$f_1(x)=\lvert x+1\rvert$, which obviously achieves its minimum value $0$ at $x=-1$.

$f_2(x)=\lvert x+1\rvert +\lvert x+2\rvert$. It can be proven that it achieves its minimum value $1$ at any point in $[-2,-1]$.

Postscript

Later, the students who took the third national exam paper once again recalled the fear of being dominated by parametric equations.

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Resources such as solutions can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5