Eastern Circles Island 以其神秘的形状而闻名：它是一个完全平坦的岛屿，其形状是由圆心位于 $x$ 轴上的若干圆及其内部区域的并集所组成的。

Eastern Circles Island 的国王计划在岛上建造一个大正方形，以庆祝他登基五十周年。国王希望这个正方形尽可能大。正方形的整个区域必须位于 Eastern Circles Island 的表面内，但岛上的任何区域都可以用于建造正方形。他还要求这个形状必须是正方形（当然！），并且正方形的至少一条边与 $x$ 轴平行。

作为 Eastern Circles Island 的大臣，你现在受命建造这个正方形。首先，国王想知道这个正方形最大能有多大。已知构成 Eastern Circles Island 的圆的位置和半径，请回答最大可能正方形的边长。

$N$ 个圆按其圆心 $x$ 坐标的升序给出。你可以假设对于所有 $i$ ($1 \le i \le N - 1$)，第 $i$ 个圆和第 $i+1$ 个圆相互重叠。你还可以假设没有圆被其他圆完全覆盖。

上图展示了 Eastern Circles Island 的形状以及样例输入中测试用例 1 的最大可能正方形之一。

输入格式

输入包含多个数据集。数据集的数量不超过 30 个。

每个数据集的第一行包含一个整数 $N$ ($1 \le N \le 50,000$)，表示构成 Eastern Circles Island 的圆的数量。接下来的 $N$ 行描述每个圆。第 $i+1$ 行包含两个整数 $X_i$ ($-100,000 \le X_i \le 100,000$) 和 $R_i$ ($1 \le R_i \le 100,000$)。$X_i$ 表示第 $i$ 个圆圆心的 $x$ 坐标，$R_i$ 表示第 $i$ 个圆的半径。每个圆的 $y$ 坐标均为 0，即第 $i$ 个圆的圆心位于 $(X_i, 0)$。

你可以做出以下假设：

• 对于所有 $i$ ($1 \le i \le N - 1$)，$X_i$ 严格小于 $X_{i+1}$。
• 对于所有 $i$ ($1 \le i \le N - 1$)，第 $i$ 个圆和第 $i+1$ 个圆至少有一个公共点 ($X_{i+1} - X_i \le R_i + R_{i+1}$)。
• 每个圆都至少有一个点不位于任何其他圆的内部或边界上。

输入的结尾由一行包含 0 的数据表示。

输出格式

对于每个数据集，输出一行，包含最大面积正方形的边长。输出的绝对误差或相对误差应不超过 $10^{-4}$。

样例

输入 1

2
0 8
10 8
2
0 7
10 7
0

输出 1

12.489995996796796
9.899494936611665