In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

The organizers of CEOI 2011 are planning to hold a party with lots of balloons. There will be balloons, all sphere-shaped and lying in a line on the floor.

The balloons are yet to be inflated, and each of them initially has zero radius. Additionally, the -th balloon is permanently attached to the floor at coordinate . They are going to be inflated sequentially, from left to right. When a balloon is inflated, its radius is increased continuously until it reaches the upper bound for the balloon, , or the balloon touches one of the previously inflated balloons.

The balloons from the example test, after being fully inflated.

The organizers would like to estimate how much air will be needed to inflate all the balloons. You are to find the final radius for each balloon.

The first line of the standard input contains one integer () - the number of balloons. The next lines describe the balloons. The -th of these lines contains two integers and (, ). You may assume that the balloons are given in a strictly increasing order of the coordinate.

In test data worth 40 points an additional inequality holds.

Your program should output exactly lines, with the -th line containing exactly one number - the radius of the -th balloon after inflating. Your answer will be accepted if it differs from the correct one by no more than for each number in the output.

For the input data:

3 0 9 8 1 13 7

the correct result is:

9.000 1.000 4.694

**Hint:**
To output a `long double` with three decimal places in C/C++ you may
use
`printf("%.3Lf\n", a);`
where `a` is the `long double` to be printed.
In C++ with streams, you may use
`cout << fixed << setprecision(3);`
before printing with `cout << a << "\n";`
(and please remember to include the `iomanip` header file).
In Pascal, you may use `writeln(a:0:3);` .
You are advised to use the `long double` type
in C/C++ or the `extended` type in Pascal,
this is due to the greater precision of these types.
In particular, in every considered correct algorithm no rounding errors
occur when using these types.

*Task author: Jakub Pachocki.*