Problem: You are given a set of circles C of a variety of radii (radiuses) placed at a variety of positions, possibly overlapping one another. Given a circle with radius r, that circle may be placed so that it encircles all of the circles in the set C if r is large enough.

There may be more than one possible position of the circle of radius r to encircle all the member circles of C. We define the region U as the union of the areas of encircling circles at all such positions. In other words, for each point in U, there exists a circle of radius r that encircles that point and all the members of C. Your task is to calculate the length of the periphery of that region U.

Figure I.1 shows an example of the set of circles C and the region U. In the figure, three circles contained in C are expressed by circles of solid circumference, some possible positions of the encircling circles are expressed by circles of dashed circumference, and the area U is expressed by a thick dashed closed curve.

<image>



Input

The input is a sequence of datasets. The number of datasets is less than 100.

Each dataset is formatted as follows.

n r
x1 y1 r1
x2 y2 r2
.
.
.
xn yn rn

The first line of a dataset contains two positive integers, n and r, separated by a single space. n means the number of the circles in the set C and does not exceed 100. r means the radius of the encircling circle and does not exceed 1000.

Each of the n lines following the first line contains three integers separated by a single space. (xi, yi) means the center position of the i-th circle of the set C and ri means its radius.

You may assume −500≤xi ≤500, −500≤yi ≤500, and 1≤ri ≤500.

The end of the input is indicated by a line containing two zeros separated by a single space.

Output

For each dataset, output a line containing a decimal fraction which means the length of the periphery (circumferential length) of the region U.

The output should not contain an error greater than 0.01. You can assume that, when r changes by ε (|ε| < 0.0000001), the length of the periphery of the region U will not change more than 0.001.

If r is too small to cover all of the circles in C, output a line containing only 0.0.

No other characters should be contained in the output.

Example

Input

1 10
5 5 7
2 12
5 5 7
8 6 3
3 10
3 11 2
2 1 1
2 16 3
3 15
-5 2 5
9 2 9
5 8 6
3 38
-25 -10 8
30 5 7
-3 35 11
3 39
-25 -10 8
30 5 7
-3 35 11
3 800
-400 400 2
300 300 1
300 302 1
3 800
400 -400 2
300 300 1
307 300 3
8 147
130 80 12
130 -40 12
-110 80 12
-110 -40 12
70 140 12
70 -100 12
-50 140 12
-50 -100 12
3 493
345 154 10
291 111 75
-275 -301 46
4 55
54 0 1
40 30 5
27 36 10
0 48 7
3 30
0 3 3
-3 0 4
400 0 3
3 7
2 3 2
-5 -4 2
-4 3 2
3 10
-5 -4 5
2 3 5
-4 3 5
4 6
4 6 1
5 5 1
1 7 1
0 1 1
3 493
345 154 10
291 111 75
-275 -301 46
5 20
-9 12 5
0 15 5
3 -3 3
12 9 5
-12 9 5
0 0


Output

81.68140899333463
106.81415022205297
74.11215318612639
108.92086846105579
0.0
254.85616536128433
8576.936716409238
8569.462129048667
929.1977057481128
4181.124698202453
505.09134735536804
0.0
46.82023824234038
65.66979416387915
50.990642291793506
4181.124698202453
158.87951420768937

Solution (in CPP):

Solution:
#include<iostream>
#include<complex>
#include<cmath>
#include<vector>
#include<iomanip>
#include<set>
#include<functional>
#include<algorithm>
#include<cstdlib>
#include<cassert>

using namespace std;

typedef double elem;
typedef complex<elem> point, vec;
typedef pair<point,point> pp;
const elem eps = 1e-8;
const elem inf = 1e40;
const elem pi = 2*acos(0.0);

#define foreach(it,o) for(__typeof((o).begin()) it = (o).begin(); (it) != (o).end(); it++)

bool eq(elem a, elem b){
  return abs(b-a)<eps;
}
bool lt(elem a, elem b){
  return !eq(a,b) && a<b;
}
bool leq(elem a, elem b){
  return eq(a,b) || a<b;
}

elem varg(const vec &a, const vec &b){
  elem ret = arg(a)-arg(b);
  if(ret<0)ret += 2*pi;
  if(ret>2*pi)ret -= 2*pi;
  if(eq(ret,2*pi))ret= 0;
  return ret;
}

struct circle{
  point c;
  elem r;
  circle():c(0,0),r(0){}
  circle(const point &c, elem r):c(c),r(r){} 
};

enum cir_rel{cir_1c=0x01,cir_1ic=0x02,cir_0c=0x04,cir_cont=0x08,cir_2c=0x10,cir_same=0x20};

int circlesRel(const circle &c1, const circle &c2){
  elem d = abs(c1.c- c2.c);
  elem r1=c1.r, r2=c2.r;
  if(lt(r1,r2))swap(r1,r2);
  if(eq(d,r1+r2))return cir_1c;
  if(eq(d,r1-r2))return cir_1ic;
  if(lt(r1+r2,d))return cir_0c;
  if(lt(d,r1-r2))return cir_cont;
  if(lt(d,r1+r2))return cir_2c;
  if(eq(abs(c1.c-c2.c),0)&&eq(c1.r,c2.r))return cir_same;
}

bool inCircle(const circle &a, const circle &b){
  return circlesRel(a,b) & (cir_1ic|cir_cont|cir_same);
}

void removeIncircles(vector<circle> &vc){
  for(int i = 0; i < (int)vc.size(); ++i){
    for(int j = i+1; j < (int)vc.size(); ++j){
      if( !lt(vc[i].r, abs(vc[i].c-vc[j].c) + vc[j].r) ){
        vc.erase( vc.begin() + j );
        j = i;
      }
    }
  }
}

vec uvec(const vec &a){ return a / abs(a); }

int intersectionCC(const circle &c1, const circle &c2, pp &p){
  if( !(circlesRel(c1,c2) & (cir_1ic|cir_1c|cir_2c)))return 0;
  elem d = abs(c1.c-c2.c);
  vec ab = c2.c- c1.c;
  elem k = (c1.r*c1.r-c2.r*c2.r+d*d) / (2*d*d);
  point t = k*ab+c1.c;
  elem x = sqrt(c1.r*c1.r-(d*d*k*k));
  
  if( eq(x,0) ){
    p.first = t; return 1;
  }else{
    p.first = x * uvec(ab*point(0,1))+t;
    p.second = x * uvec(ab*point(0,-1))+t;
    return 2;
  }
}

bool checkAll(const circle &c, const vector<circle> &vc){
  for(int i = 0; i < (int)vc.size(); ++i){
    if( lt(c.r, abs(vc[i].c-c.c)+vc[i].r ) ) return false;
  }
  return true;
}

int getEncirclingCircle(elem r, const circle &c1, const circle &c2, const vector<circle> &vc,
                        pair<circle,circle> &ret){
  circle x(c1.c, r-c1.r);
  circle y(c2.c, r-c2.r);

  pp p;
  int cc_ret = intersectionCC(x,y,p);
  if( cc_ret == 1 ){
    ret.first = circle(p.first,r);
    if( !checkAll(ret.first, vc) ) cc_ret--;
  }else if( cc_ret == 2 ){
    ret.first = circle(p.first,r);
    ret.second = circle(p.second,r);
    if( !checkAll(ret.first, vc) ){ cc_ret--; ret.first = ret.second;
    }else if( !checkAll(ret.second, vc) ) cc_ret--;
    if( !checkAll(ret.first, vc) ) cc_ret--;
  }
  return cc_ret;
}

struct bc{
  int corr;
  point center;
  point corr_c;

  bc(int corr, point center, point corr_c):corr(corr),center(center),corr_c(corr_c){}
};

struct cmp{
  point center;
  cmp(point c):center(c){}
  //bool operator()(const point &a, const point &b)const{
  //return varg(point(1,0),a-center)<varg(point(1,0),b-center);
  //}
  //bool operator()(const circle &a, const circle &b)const{
  //return varg(point(1,0),a.c-center)<varg(point(1,0),b.c-center);
  //}
  bool operator()(const bc &a, const bc &b)const{
    assert(abs(a.corr_c-center)>0);
    assert(abs(b.corr_c-center)>0);

    // elem tmp_a = varg(point(1,0),a.corr_c-center);
    //elem tmp_b = varg(point(1,0),b.corr_c-center);
    elem tmp_a = arg(a.corr_c-center);
    elem tmp_b = arg(b.corr_c-center);
    if(!eq(tmp_a,tmp_b))return tmp_a<tmp_b;
    //if(a.corr!=b.corr)return a.corr<b.corr;
    return false;
  }
};

int main()
{
  int n;
  elem R;

  while( cin >> n >> R ){

    if( n == 0 && eq(R,0) ) break;
    
    vector<circle> vc;
    elem res = 0;
    point cog;

    for(int i = 0; i < n; ++i){
      elem x,y,r;
      cin >> x >> y >> r;
      vc.push_back( circle(point(x,y),r) );
    }

    removeIncircles( vc );
    n = vc.size();

    // cout << setprecision(3);
    for(int i = 0; i < (int)vc.size(); ++i){
      // cout << "circle("<<vc[i].c.real()<<","<<vc[i].c.imag()<<","<<vc[i].r<<");"<<endl;
      cog += vc[i].c;
    }
    cog = cog * (1./vc.size());
    // cout << endl;
    
    if( n == 1 ){
      if( !lt(R,vc.front().r) ){
        res = 2*pi * (2*R - vc.front().r);
      }
    }else if( n >= 2 ){
      vector<bc> blueCircles;

      for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
          pair<circle,circle> tmp;
          int ret = getEncirclingCircle(R,vc[i],vc[j],vc,tmp);
          if(ret>=1){
            point pc0 = (R/(abs(tmp.first.c-vc[i].c))) * (tmp.first.c-vc[i].c) + tmp.first.c;
            point pc1 = (R/(abs(tmp.first.c-vc[j].c))) * (tmp.first.c-vc[j].c) + tmp.first.c;
            blueCircles.push_back( bc(i,tmp.first.c,pc0) );
            blueCircles.push_back( bc(j,tmp.first.c, pc1));
          }
          if(ret>=2){
            point pc0 = (R/(abs(tmp.second.c-vc[i].c))) * (tmp.second.c-vc[i].c) + tmp.second.c;
            point pc1 = (R/(abs(tmp.second.c-vc[j].c))) * (tmp.second.c-vc[j].c) + tmp.second.c;
            blueCircles.push_back( bc(i,tmp.second.c,pc0) );
            blueCircles.push_back( bc(j,tmp.second.c,pc1) );
          }
        }
      }
      
      if( blueCircles.size() == 0 ){
        cout << 0 << endl;
        //cout << "EMPTY" << endl;
        continue;
      }
      assert(blueCircles.size()>0);
      
      sort(blueCircles.begin(), blueCircles.end(), cmp(blueCircles.front().center));
      
      // int cid[blueCircles.size()];
      // cid[0] = 0;
      point prev_center = blueCircles.front().center;
      
      for(int i = 0; i < (int)blueCircles.size(); ++i){
        bc i0 = blueCircles[i];
        bc i1 = blueCircles[(i+1)%blueCircles.size()];

        /*
        if(i>0){
          if( !eq(abs(prev_center - i0.center),0) ){
            prev_center = i0.center;
            cid[i] = cid[i-1]+1;
          }else{
            cid[i] = cid[i-1];
          }
        }
        */
        
        // if( eq(abs(i0.center-i1.center),0) ){
          if( i0.corr != i1.corr ){
            // cout << i << ' ' << i+1 << endl;
            elem tmp = varg( vc[i0.corr].c - i0.center, vc[i1.corr].c - i0.center);
            if( lt(pi, tmp) ) tmp = 2*pi - tmp;
            
            tmp=abs(arg( (i0.corr_c-i0.center)/(i1.corr_c-i1.center)));
            // (vc[i0.corr].c - i0.center) );
            res += tmp * R;
          }
          //}else{
          else if( i0.corr == i1.corr ){
            elem tmp = abs(arg( (i0.center - vc[i0.corr].c)));
            tmp = abs(arg((i0.corr_c-vc[i0.corr].c)/(i1.corr_c-vc[i0.corr].c)));
            //- vc[i0.corr].c );
            res += tmp * (2*R-vc[i0.corr].r);
          }
          //}
      }

      /*
      cout << blueCircles.size() << endl;
      for(int i = 0; i < (int)blueCircles.size(); ++i){
        cout <<cid[i]<<' ' <<blueCircles[i].corr<<
          ' ' << "circle("<<blueCircles[i].center.real()<<
          ","<<blueCircles[i].center.imag()<<","<<R<<");"<<endl;
      }
      cout << "---"<<endl;
      */

      /*
      set<pair<int,pair<int,int> > > S;
      for(int i = 0; i < (int)blueCircles.size(); ++i){
        bc i0 = blueCircles[i];
        int prev_cid = cid[i];
        int diff = 0;
        
        for(int j = i+1; j < 2*(int)blueCircles.size(); ++j){          
          bc j0 = blueCircles[j%blueCircles.size()];
          if( prev_cid != cid[j%blueCircles.size()] ){
            prev_cid = cid[j%blueCircles.size()];
            ++diff;
          }
          if(diff==2)break;

          if( !eq( abs(i0.center-j0.center), 0) ){
            if( i0.corr == j0.corr ){
              pair<int,int> stp = make_pair(cid[i],cid[j%blueCircles.size()]);
              if(stp.first>stp.second)swap(stp.first,stp.second);
              pair<int, pair<int,int> > st = make_pair(i0.corr,stp);
              if( S.find(st)==S.end()){
                // cout << i << ' ' << j << endl;
                S.insert(st);
                
                //elem tmp = varg( i0.center - vc[i0.corr].c, j0.center - vc[i0.corr].c );
                elem tmp = arg(i0.center - vc[i0.corr].c);
                // , j0.center-vc[i0.corr].c);
                if( lt(pi, tmp) ) tmp = 2*pi - tmp;
                // res += tmp * (2*R - vc[i0.corr].r);
                break;
              }
            }

          }
        }
      }
      */

    }

    cout << fixed << setprecision(16) << res << endl;
  }
  return 0;
}