Square in Circles

Circles Island is completely flat. Its shape is the union of several circles together with their interiors, and every circle has its center on the x-axis.

The king of Circles Island wants to build a large square plaza for the fiftieth anniversary of his accession, and he wants the plaza as large as possible. The whole plaza must lie on the island, and any part of the island may be used. The plaza must be a square, and one of its sides must be parallel to the x-axis.

You are given the center and the radius of every circle that forms the island. Report the side length of the largest square that can be built.

The circles are given in increasing order of the x-coordinate of their centers. For every $i$ $(1 \le i \le N-1)$, circle $i$ and circle $i+1$ overlap. No circle is completely covered by the other circles.

Figure 1. The island of the first example and one of its largest squares

The input has several datasets, at most 30 of them. Each dataset is in this format.

N
X1 R1
:
XN RN

The first line of a dataset has one integer $N$ $(1 \le N \le 50000)$, the number of circles that form the island. Line $i$ of the next $N$ lines has two integers $X_i$ $(-100000 \le X_i \le 100000)$ and $R_i$ $(1 \le R_i \le 100000)$. Circle $i$ has its center at $(X_i, 0)$ and its radius is $R_i$.

You may assume the following.

• $X_i < X_{i+1}$ for every $i$ $(1 \le i \le N-1)$.
• Circle $i$ and circle $i+1$ share at least one point for every $i$ $(1 \le i \le N-1)$, that is, $X_{i+1} - X_i \le R_i + R_{i+1}$.
• Every circle has at least one point that is neither inside nor on the boundary of any other circle.

The end of the input is a line that holds a single zero.

For each dataset, print the side length of the largest square on its own line, rounded to six digits after the decimal point.