Problem: Problem Statement

Circles Island is known for its mysterious shape: it is a completely flat island with its shape being a union of circles whose centers are on the $x$-axis and their inside regions.

The King of Circles Island plans to build a large square on Circles Island in order to celebrate the fiftieth anniversary of his accession. The King wants to make the square as large as possible. The whole area of the square must be on the surface of Circles Island, but any area of Circles Island can be used for the square. He also requires that the shape of the square is square (of course!) and at least one side of the square is parallel to the $x$-axis.

You, a minister of Circles Island, are now ordered to build the square. First, the King wants to know how large the square can be. You are given the positions and radii of the circles that constitute Circles Island. Answer the side length of the largest possible square.

$N$ circles are given in an ascending order of their centers' $x$-coordinates. You can assume that for all $i$ ($1 \le i \le N-1$), the $i$-th and $(i+1)$-st circles overlap each other. You can also assume that no circles are completely overlapped by other circles.

<image>

[fig.1 : Shape of Circles Island and one of the largest possible squares for test case #1 of sample input]

Input

The input consists of multiple datasets. The number of datasets does not exceed $30$. Each dataset is formatted as follows.

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

The first line of a dataset contains a single integer $N$ ($1 \le N \le 50{,}000$), the number of circles that constitute Circles Island. Each of the following $N$ lines describes a circle. The $(i+1)$-st line contains two integers $X_i$ ($-100{,}000 \le X_i \le 100{,}000$) and $R_i$ ($1 \le R_i \le 100{,}000$). $X_i$ denotes the $x$-coordinate of the center of the $i$-th circle and $R_i$ denotes the radius of the $i$-th circle. The $y$-coordinate of every circle is $0$, that is, the center of the $i$-th circle is at ($X_i$, $0$).

You can assume the followings.

* For all $i$ ($1 \le i \le N-1$), $X_i$ is strictly less than $X_{i+1}$.
* For all $i$ ($1 \le i \le N-1$), the $i$-th circle and the $(i+1)$-st circle have at least one common point ($X_{i+1} - X_i \le R_i + R_{i+1}$).
* Every circle has at least one point that is not inside or on the boundary of any other circles.



The end of the input is indicated by a line containing a zero.

Output

For each dataset, output a line containing the side length of the square with the largest area. The output must have an absolute or relative error at most $10^{-4}$.

Sample Input


2
0 8
10 8
2
0 7
10 7
0

Output for the Sample Input


12.489995996796796
9.899494936611665





Example

Input

2
0 8
10 8
2
0 7
10 7
0


Output

12.489995996796796
9.899494936611665

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

static const int    INF = 1000000000;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-8;

template<typename T> T add(T x, T y){ if(abs(x+y) < EPS*(abs(x)+abs(y))) return 0; return x + y; }
template<typename T> inline bool semieq(T x, T y){ return abs(x - y) < EPS; }
template<typename T> inline bool semige(T x, T y){ return y - x < -EPS; }
template<typename T> inline bool semile(T x, T y){ return x - y < -EPS; }


struct Point : public complex<double>
{
public:
  Point(const double x = 0.0, const double y = 0.0) { this->real(x);  this->imag(y); }
  Point(const complex<double> w)  { this->real(w.real());  this->imag(w.imag()); }
  inline double dot(Point p){ return (conj(*this) * p).real(); }  // ??????
  inline double det(Point p){ return (conj(*this) * p).imag(); }  // ??????
};

namespace std
{
  inline bool operator < (const Point& a, const Point& b)
  {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
typedef vector<Point> Polygon;
inline Point currPoint(vector<Point> P, int i){ return P[i]; }
inline Point nextPoint(vector<Point> P, int i){ return P[(i+1)%P.size()]; }
inline Point diffPoint(vector<Point> P, int i){ return nextPoint(P, i) - currPoint(P, i); }


int ccw(Point a, Point b, Point c)
{
  b -= a;
  c -= a;
  if(b.det(c) > 0.0)    return  1;         // counter clockwise
  if(b.det(c) < 0.0)    return -1;         // clockwise
  if(b.dot(c) < 0.0)    return  2;         // c--a--b on line
  if(norm(b) < norm(c)) return -2;         // a--b--c on line
  return 0;
}


struct Circle : Point
{
private:
  Point p;
  double r;

public:
  Circle() : p(Point(0.0, 0.0)), r(0.0) {}
  Circle(Point p, double r) : p(p), r(r) {}
  Circle(double x, double y, double r) : p(Point(x, y)), r(r) {}
  inline Point center(){ return this->p; }
  inline double radius(){ return this->r; }
};


vector<Point> intersectionOfCC(Circle A, Circle B)
{
  vector<Point> ret(2);
  double x1 = A.center().real(), y1 = A.center().imag(), r1 = A.radius();
  double x2 = B.center().real(), y2 = B.center().imag(), r2 = B.radius();
  double dx = x2 - x1;
  double dy = y2 - y1;
  double a = dx * dx + dy * dy;
  double b = ((r1 * r1 - r2 * r2) / a + 1) / 2;
  double d = r1 * r1 / a - b * b;
  double x3 = x1 + dx * b;
  double y3 = y1 + dy * b;
  double x4 = -dy * sqrt(d);
  double y4 =  dx * sqrt(d);
  ret[0] = Point(x3 - x4, y3 - y4);
  ret[1] = Point(x3 + x4, y3 + y4);
  return ret;
}


int N;
double X, R;
Circle* C;

bool check(double d)
{
  deque<int> deq;
  int pos = 0;
  deq.pb(pos++);
  while(!deq.empty()){
    int f = deq.front();
    Point c = C[f].center();
    double hx = c.real();
    double hr = C[f].radius();
    if(semile(hr, d / 2.0)){
      deq.pop_front();
      if(pos < N) deq.pb(pos++);
      continue;
    }
    double x = hx - sqrt(hr * hr - d * d / 4.0);
    Point np = Point(x + d, d / 2.0);
    if(!semige(abs(c - np), hr)) return true;
    int sz = deq.size();
    int t1 = deq.at(sz - 1);
    if(sz > 1){
      int t2 = deq.at(sz - 2);
      vector<Point> in = intersectionOfCC(C[t1], C[t2]);
      double y = max(in[0].imag(), in[1].imag());
      if(!semige(abs(C[t1].center() - np), C[t1].radius()))
        if(!semige(d / 2.0, y)) return true;
      if(semile(y, d / 2.0)){
        deq.pop_front();
        continue;
      }
    }
    if(pos >= N) deq.pop_front();
    if(pos < N) deq.pb(pos++);
  }
  return false;
}

int main(int argc, char *argv[])
{
  while(cin >> N, N){
    C = new Circle[N];
    double l = 0.0;
    double r = INF;
    rep(i, N){
      cin >> X >> R;
      C[i] = Circle(X, 0.0, R);
      maxup(l, R);
    }

    rep(_, 100){
      double mid = (l + r) / 2.0;
      if(check(mid)) l = mid;
      else r = mid;
    }

    printf("%.15f\n", r);
    
    delete[] C;
  }
  
  return 0;
}