卡罗尔目前正在进行冰壶运动。
她在 2D 平面上有 n 个圆盘,每个圆盘的半径为 r。
最初,她拥有 y = 10100 线上方的所有这些磁盘。
然后,她将按照从 1 到 n 的顺序将圆盘向 y = 0 线滑动。
当她滑动第 i 个圆盘时,她会将其中心放置在点 (xi, 10100) 上。然后她将推动它,使圆盘的 y 坐标不断减小,而 x 坐标保持不变。一旦接触到线 y = 0 或接触到任何先前的圆盘,圆盘就会停止。请注意,一旦磁盘停止移动,即使被另一个磁盘击中,它也不会再次移动。
计算所有磁盘被推送后的所有磁盘中心的 y 坐标。
输入
第一行将包含两个整数 n 和 r (1 ≤ n, r ≤ 1 000),分别是圆盘的数量和圆盘的半径。
下一行将包含 n 个整数 x1, x2, ..., xn (1 ≤ xi ≤ 1 000) - 磁盘的 x 坐标。
输出
打印一行包含 n 个数字的内容。第 i 个数字表示第 i 个圆盘中心的 y 坐标。如果输出的绝对或相对误差最多为 10 - 6,则输出将被接受。
也就是说,假设您对特定坐标值的答案是 a,陪审团的答案是 b。如果所有坐标的 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$ ,检查程序将认为您的答案正确。
示例
输入 #1
6 2 5 5 6 8 3 12
输出 #1
2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613
注意
磁盘的最终位置如下所示:
特别要注意最后一个磁盘的位置。