Minimizing Cumulative Absolute Linear Functions

Time rewinds to June 7, 2017. It’s a sunny afternoon and you find yourself in the examination hall, furiously writing down answers that will reach both your past and future selves. As always, you quickly jump to the last big problem of the math test—a choice between two problems where you opt for the second one. Skimming the problem description, your tense brow relaxes with confidence. "It’s all under control," you think, and you take another step toward 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 for each \(k=1,2,\dots,n\) the function:

$$\displaystyle f_k(x)=\sum_{i=1}^{k}\big|a_ix+b_i\big|.$$

Your task is to compute, for every \(k\) from 1 to \(n\), the minimum value of \(f_k(x)\) for \(x\in\mathbb{R}\). It can be proved that a minimum value always exists.

inputFormat

The input consists of three lines:

• The first line contains an integer \(n\) (e.g. \(1 \le n \le 10^5\)).
• The second line contains \(n\) real numbers representing the vector \(a\): \(a_1, a_2, \dots, a_n\).
• The third line contains \(n\) real numbers representing the vector \(b\): \(b_1, b_2, \dots, b_n\).

outputFormat

Output \(n\) numbers separated by spaces. The \(k\)-th number should be the minimum value of \(f_k(x)\) over all real \(x\). Answers with an absolute or relative error of at most \(10^{-6}\) are accepted.

sample

1
1
0

0.000000