After the Contest: Balloons

Time limit1sMemory limit128 MB

Summary

Simulate balloons inflated left to right on a line, each stopping at its max radius or when it touches an earlier balloon, and output the final radii efficiently.

Level: Medium7 of 10
Topics: Binary search, Geometry, Stack
Solved: No attempts yet

Problem

After finishing the preparations for CEOI 2011, you feel like throwing a party. Actually, more than a party, you want to blow up balloons. There are $n$ perfectly spherical balloons lying on the ground.

They have not been inflated yet, so each balloon starts with radius $0$ . The $i$ -th balloon is fixed at coordinate $x_i$ ; it can neither move nor float away. The balloons are inflated one by one from left to right. Each balloon grows until it reaches its maximum radius $r_i$ , or until it touches another balloon that was inflated earlier.

Figure 1: all balloons of the example after being inflated.

Determine the final radius of every balloon.

Input

The first line contains the number of balloons $n$ ( $1 \le n \le 200\,000$ ).

Each of the next $n$ lines describes one balloon: the $i$ -th of these lines contains two integers $x_i$ and $r_i$ separated by a space. Here $x_i$ is the coordinate where the balloon sits ( $0 \le x_i \le 10^9$ ) and $r_i$ is the maximum radius that balloon may reach ( $1 \le r_i \le 10^9$ ). The balloons are given from left to right and the coordinates are strictly increasing, i.e. $x_1 < x_2 < \dots < x_n$ .

Output

Print $n$ lines. The $i$ -th line must contain the final radius of the $i$ -th balloon, rounded to exactly $3$ decimal places.

Examples2

Example 1
Input
```
3
0 9
8 1
13 7
```
Expected output
```
9.000
1.000
4.694
```
Example 2
Input
```
2
0 10
6 10
```
Expected output
```
10.000
0.900
```