Holey Road

你正在操控一辆小型遥控车在路况极差的道路上行驶，道路上布满了坑洞。车辆无法驶过这些坑洞，否则会掉进去并彻底损坏。此外，驶出道路会导致车辆永远迷失在周围的高草丛中。

车辆非常小，可以被视为一个没有空间延伸的点。道路宽 $W$ 米，长 $L$ 米，且平行于 $y$ 轴。你的车起始位置为 $(\frac{W}{2}, 0)$，目的地为 $(\frac{W}{2}, L)$。所有的坑洞都是完美的圆形，且没有任何坑洞会与其他坑洞或道路边缘相交或接触。

你希望走最短的路径到达目的地。编写一个程序来计算这条路径的长度。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含三个整数 $N, W, L$，分别表示坑洞的数量、道路的宽度和长度。接下来 $N$ 行，每行包含三个整数 $x_i, y_i, r_i$，表示一个圆心为 $(x_i, y_i)$、半径为 $r_i$ 的坑洞。

输出格式

对于每个测试用例，输出从起点到终点避开所有坑洞的最短路径长度。输出结果允许有 $10^{-6}$ 的误差。

数据范围

• $0 < T \le 100$
• $0 \le N \le 100$
• $0 < L \le 1000$
• $0 < W \le 100$
• $r_i < x_i < W - r_i$
• $r_i < y_i < L - r_i$
• $0 < r_i < \min (\frac{W}{2}, \frac{L}{2})$

样例

输入格式 1

3
1 50 1000
20 500 5
1 50 1000
25 500 5
3 100 1000
50 50 25
25 150 24
75 150 24

输出格式 1

1000.00000000000
1000.05000041668
1009.34797846036