题目描述

在 Counter Strike（反恐精英）的 cs_assault 地图里有这样的场景：

图中的管道是外界进入这个仓库的路径之一。但是这条管道十分狭窄，遭枪击时根本无法躲避，于是 gx 就拿了一把枪守在管道的这一端，一旦对面出现敌人就马上开枪。导致试图从此处经过的敌人无一幸免。

对方纷纷表示用这种方式防守太无聊了，他们对这个管道进行了一些修改。我们用三维直角坐标系描述这个管道，如下图所示：

1. 管道从 $y$ 轴负方向延伸到 $y$ 轴正方向。
2. 称x轴负方向为左边， $x$ 轴正方向为右边，$z$ 轴正方向为上边，$z$ 轴负方向为下边。
3. 管道是由若干四棱柱拼接而成，每个四棱柱的两个底面都是边长为 $1$ 的正方形，且这两个底面都平行于 $\mathrm{xoz}$ 平面。也就是说，对于管道的任何一个垂直于y轴的的截面，它都是正方形，只要知道右上角顶点的坐标 $(x,y,z)$ 就可以知道正方形剩下三个点的坐标 $(x-1,y,z), (x,y,z-1), (x-1,y,z-1)$。
4. 知道了管道右上方的折线，通过向左平移 $1$ 、再向下平移 $1$ 、再向右平移 $1$ ，再向上平移 $1$ ，可以得到该管道的边界。所以给出管道右上方的折线的每个顶点的坐标，我们就可以确定整个管道的形状。

对于 gx 的枪，有如下说明:

1. gx 的枪沿一条直线射出一颗子弹。我们把子弹视作是一个半径为 $r$ 的圆，所以轨迹可以视作一个底面半径为 $r$ 的狭长圆柱。对于某个 $y=y_0$ 的截面，如果子弹能够完整地通过，称此处是被 gx 控制的。反之，子弹在接触目标前会发生偏折，因此该截面是不被控制的。子弹刚好擦边而过的情况也算作可以通过。
2. gx 站在 $y$ 轴负方向的那一端，面向 $y$ 轴正方向。 gx 的枪可以在管道外任何位置以任何角度，从 $y$ 轴负方向向 $y$ 轴正方向进行瞄准。 现在面对这个蜿蜒曲折的管道，gx想知道他能控制的最远截面的 $y$ 坐标值是多少。

输入格式

输入的第一行包含整数 $n$ 和实数 $r$ 。接下来 $n$ 行每行三个实数，第 $i$ 行的三个实数表示第 $i$ 个正方形右上角顶点的坐标 $(x, y, z)$ 。输入保证 $y$ 坐标值是严格递增的。

输出格式

输出一个实数，表示最远的控制点。保留三位小数。数据保证 gx 的子弹不能贯穿整个管道。

5 0
0.0 -2.0 1.0
0.0 0.0 1.0
1.0 1.0 0.0
0.0 1.5 1.0
2.0 3.0 0.0

2.250

3 0.2
0.0 0.0 1.0
0.0 1.0 1.0
2.0 2.0 -1.0

1.374

数据规模与约定

对于 $100\%$ 的数据，$3\le n\le 2\times 10^4$ ， $0\le r\le 0.5$，$-10^5\le x_i, y_i, z_i\le 10^5$

均匀分布着 $50\%$的数据 $r=0$

样例说明

样例 $1$ 说明：

沿 $y$ 轴正方向，最远可以控制到 $y=2.250$ （图示见问题描述）