The team “Lvl 5. Dagon” has a strange habit while they’re competing. They put balloons in a line on the floor. Once they pass one problem, they instantly inflate one balloon, from left to right.
The balloons are yet to be inflated, and each of them initially has zero radius. Additionally, the i-th balloon is permanently attached to the floor at coordinate Xi. 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, Ri, or the balloon touches one of the previously inflated balloons.
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 input consists of several test cases, terminates with EOF.
The first line of the standard input contains one integer N (1 <= N <= 200,000) - the number of balloons. The next N lines describe the balloons. The i_th of these lines contains two integers Xi and Ri (0 <= Xi <= 109, 1 <= Ri <= 109). You may assume that the balloons are given in a strictly increasing order of the X coordinate.
For every test case, your program should output exactly N lines, with the i_th line containing exactly one number - the radius of the i_th balloon after inflating. Your answer will be accepted if it differs from the correct one by no more than 0.001 for each number in the output.
Please output a blank line after every test case.
3 0 9 8 1 13 7 3 0 9 8 1 13 7
9.000 1.000 4.694 9.000 1.000 4.694
Info: 本題輸出為浮點數，絕對或相對誤差 1e-3 以下視為正確
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|