CEOI 2011 的组织者们正计划举办一场有很多气球的派对。将会有 $n$ 个气球，它们都是球形的，并且在地面上排成一条线。

这些气球尚未被充气，每个气球的初始半径均为零。此外，第 $i$ 个气球被永久固定在地面上坐标为 $x_i$ 的位置。它们将按照从左到右的顺序依次被充气。当一个气球被充气时，它的半径会连续增大，直到达到该气球的半径上限 $r_i$，或者该气球触碰到之前已经充气的某个气球为止。

图 1：样例测试中的气球完全充气后的示意图。

组织者们想要估算充气所有气球需要多少空气。你的任务是求出每个气球最终的半径。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$) —— 气球的数量。

接下来的 $n$ 行描述这些气球。其中第 $i$ 行包含两个整数 $x_i$ 和 $r_i$ ($0 \le x_i \le 10^9$，$1 \le r_i \le 10^9$)。你可以认为气球是按照 $x$ 坐标严格递增的顺序给出的。

在占分 40 分的测试数据中，满足额外限制 $n \le 2\,000$。

输出格式

你的程序应该输出恰好 $n$ 行，其中第 $i$ 行包含恰好一个实数 —— 第 $i$ 个气球充气后的最终半径。如果输出中每个数与正确答案的绝对误差不超过 $0.001$，则你的答案将被接受。

样例

输入样例 1

3
0 9
8 1
13 7

输出样例 1

9.000
1.000
4.694

说明

提示：在 C/C++ 中输出保留三位小数的 long double 类型，你可以使用 printf("%.3Lf\n", a);，其中 a 是要打印的 long double 变量。在 C++ 中使用流（streams），你可以在使用 cout << a << "\n"; 打印之前使用 cout << fixed << setprecision(3);（请记得包含 <iomanip> 头文件）。在 Pascal 中，你可以使用 writeln(a:0:3);。建议在 C/C++ 中使用 long double 类型，在 Pascal 中使用 extended 类型，这是因为这些类型具有更高的精度。特别地，在所有被认为是正确的算法中，使用这些类型时不会发生舍入误差。