Description

There are $n$ balloons, and they are all empty at the beginning.

Next, they will be inflated one by one in order from $1$ to $n$. The $i$-th balloon touches the ground at position $x_i$.

A balloon stops inflating when it touches some previous balloon, or when it reaches its maximum radius limit. The maximum radius limit of the $i$-th balloon is $r_i$.

Now, please find the final radius of each balloon.

Input Format

The first line contains a positive integer $n$, which represents the number of balloons.

The next $n$ lines each contain two integers $x_i, r_i$ separated by a space.

Output Format

Output $n$ lines. Each line contains a floating-point number. The floating-point number on the $i$-th line represents the final radius of the $i$-th balloon.

Your answer will be judged correct if and only if the absolute error from the correct answer does not exceed $10^{-3}$.

3
0 9
8 1
13 7

9.000
1.000
4.694

Hint

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 200\,000$, $0 \le x_i \le 10^9$, $1 \le r_i \le 10^9$, and $x_1 < x_2 < \cdots < x_n$.

Translated by ChatGPT 5