题目描述

有 $n$ 个气球，他们一开始都是空的。
接下来，它们会按照从 $1$ 到 $n$ 的顺序依次充气，其中第 $i$ 个气球与地面在 $x_i$ 位置接触。
当气球碰到碰到前面的某个气球，或者达到半径最大限制时，就会停止充气。其中第 $i$ 个气球的半径最大限制为 $r_i$。
现在请你求出，每个气球最终半径是多少。

输入格式

第一行一个正整数 $n$，表示气球个数。
接下来 $n$ 行，每行两个空格隔开的整数 $x_i,r_i$。

输出格式

输出 $n$ 行，每行一个浮点数，第 $i$ 行的浮点数表示最终第 $i$ 个气球的半径。
你的答案会被判为正确，当且仅当与答案的绝对误差不超过 $10^{-3}$。

3
0 9
8 1
13 7

9.000
1.000
4.694

数据范围与提示

对于 $40\%$ 的数据，保证 $n\le 2\ 000$；
对于 $100\%$ 的数据，保证 $1\le n\le 200\ 000;0\le x_i\le 10^9;1\le r_i\le 10^9;x_1< x_2< \cdots < x_n$。