问题描述

Circles Island以其神秘的形状而闻名：它是一个完全平坦的岛屿，其形状是圆的并集，这些圆的圆心在$x$轴上，内部区域也包括在内。

Circles Island的国王计划在Circles Island上建造一个大广场，以庆祝他登位50周年纪念日。国王希望尽可能地扩大广场的面积。整个广场的面积必须位于Circles Island的表面，但可以使用Circles Island的任何区域。国王还要求广场的形状为正方形（当然！），且至少有一边与$x$轴平行。

作为Circles Island的大臣，您现在被命令建造广场。首先，国王想要知道广场的最大可能尺寸。给定构成Circles Island的圆的位置和半径，请回答最大可能正方形的边长。

输入数据中给出了$N$个圆，按照它们的圆心$x$坐标的升序排列。您可以假设对于所有$i$（$1 \le i \le N-1$），第$i$个和$(i+1)$个圆相互重叠。您还可以假设没有圆完全重叠。

图1：Circles Island的形状和样本输入示例的可能最大正方形之一

输入

输入包含多个数据集。数据集的数量不超过30个。每个数据集的格式如下所示。

$N$
$X_1$ $R_1$
:
:
$X_N$ $R_N$

数据集的第一行包含一个整数$N$（$1 \le N \le 50,000$），表示构成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}$）。
• 每个圆至少有一个点不在其他圆的内部或边界上。

输入的结束由包含零的一行表示。

输出

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

样例输入

2
0 8
10 8
2
0 7
10 7
0```

### 样例输入对应的输出

```plain
12.489995996796796
9.899494936611665```

---

### 数据来源

JAG Practice Contest for ACM-ICPC Asia Regional 2014