Balloon Inflation

You are given n balloons. Initially, each balloon is deflated. They are inflated one by one in the order from 1 to n. The i-th balloon touches the ground at point \(x_i\) and has a maximum allowed radius of \(r_i\). When balloon i is inflating, it will stop inflating as soon as one of the following events happens:

1. It reaches its maximum radius \(r_i\), or
2. It touches one of the previously inflated balloons.

All balloons are assumed to be circles that touch the ground. In a balloon with final radius \(R\) (which may be less than or equal to its maximum radius), the circle is positioned so that its bottom touches the ground, meaning its center is at \((x_i, R)\). For two balloons \(i\) and \(j\) (with \(j < i\)) having centers \((x_i, R_i)\) and \((x_j, R_j)\) respectively, they are just touching if the distance between their centers equals \(R_i+R_j\). That is, they satisfy \[ \sqrt{(x_i-x_j)^2+(R_i-R_j)^2} = R_i+R_j. \]

Simplifying the above equation for the moment when the i-th balloon touches the j-th (with already fixed final radius \(R_j\)), we obtain:

\[ (x_i-x_j)^2 = 4 R_i R_j \quad \Longrightarrow \quad R_i = \frac{(x_i-x_j)^2}{4R_j}. \]

Thus, when inflating balloon i, for every previously inflated balloon j (with final radius \(R_j\)), a potential collision would occur when \(R_i\) reaches \(\frac{(x_i-x_j)^2}{4R_j}\). The actual final radius \(R_i\) is the minimum between its maximum \(r_i\) and all such potential collision radii:

\[ R_i = \min\Bigl( r_i, \min_{1\le j < i} \frac{(x_i-x_j)^2}{4R_j} \Bigr). \]

Your task is to compute the final radius for each balloon.

inputFormat

The first line contains a single integer n (the number of balloons). The second line contains n space-separated numbers \(x_1, x_2, \ldots, x_n\) representing the x-coordinates at which the balloons touch the ground. The third line contains n space-separated numbers \(r_1, r_2, \ldots, r_n\) representing the maximum allowed radii for each balloon.

outputFormat

Output n numbers separated by spaces: the final radius of each balloon in the order from 1 to n. Answers within a relative or absolute error of 10^{-6} are accepted.

sample

2
0 4
10 10

10 0.4