Carol is currently curling.

She has n disks each with radius r on the 2D plane. 

Initially she has all these disks above the line y = 10^100.

She then will slide the disks towards the line y = 0 one by one in order from 1 to n. 

When she slides the i-th disk, she will place its center at the point (x_{i}, 10^100). She will then push it so the disk’s y coordinate continuously decreases, and x coordinate stays constant. The disk stops once it touches the line y = 0 or it touches any previous disk. Note that once a disk stops moving, it will not move again, even if hit by another disk. 

Compute the y-coordinates of centers of all the disks after all disks have been pushed.


-----Input-----

The first line will contain two integers n and r (1 ≤ n, r ≤ 1 000), the number of disks, and the radius of the disks, respectively.

The next line will contain n integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 1 000) — the x-coordinates of the disks.


-----Output-----

Print a single line with n numbers. The i-th number denotes the y-coordinate of the center of the i-th disk. The output will be accepted if it has absolute or relative error at most 10^{ - 6}.

Namely, let's assume that your answer for a particular value of a coordinate is a and the answer of the jury is b. The checker program will consider your answer correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$ for all coordinates.


-----Example-----
Input
6 2
5 5 6 8 3 12

Output
2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613



-----Note-----

The final positions of the disks will look as follows: [Image] 

In particular, note the position of the last disk.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

n, r = map(int, input().split())
xs = list(map(int, input().split()))

points = []

for x in xs:
  y = r
  for x0, y0 in points:
    if abs(x - x0) <= 2 * r:
      y = max(y, y0 + ((2*r)**2 - (x-x0)**2)**0.5)
  points.append((x, y))

print(" ".join("%.20f" % p[1] for p in points))

n,r = list(map(int,input().split()))
X = [int(x) for x in input().split()]

Y = []
for i in range(n):
    forcedy = r
    for j in range(len(Y)):
        dist = abs(X[i]-X[j])
        if dist <= 2*r:
            y = Y[j] + ((2*r)**2-dist**2)**.5
            forcedy = max(y,forcedy)
    Y.append(forcedy)
print(*Y)
        


from math import sqrt
n, r = list(map(int, input().split()))
x = list(map(int, input().split()))
y = []
for i in range(n):
    y.append(r)
    for j in range(i):
        d = abs(x[i] - x[j])
        if d > 2 * r:
            continue
        inc = sqrt(4 * r * r - d * d)
        y[i] = max(y[i], y[j] + inc)
print(' '.join(map(str, y)))


from math import sqrt
n, r = list(map(int, input().split()))
r2 = r**2
*X, = list(map(int, input().split()))
Y = [0]*n
ans = []
for i in range(n):
    y = r
    for j in range(i):
        diff = abs(X[i] - X[j])
        if diff == 2*r:
            y = max(y, Y[j])
        elif diff < 2*r:
            y = max(y, sqrt(4*r2 - diff**2) + Y[j])
    Y[i] = y
    ans.append("%.010f" % Y[i])
print(*ans)


import math
def collide(x1,r1,x2,r2,y2):
    y = r1
    D = (r1+r2)**2-(x1-x2)**2
    if D>=0:
        y = max(y,math.sqrt(D)+y2)
    return y
n,r = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
Y = []
for i in range(n):
    y = r
    for j in range(i):
        y = max(y,collide(X[i],r,X[j],r,Y[j]))
    Y.append(y)
print(*Y)


from math import *
n, m = input().split()
n = int(n)
m = int(m)
xcenters = [int(i) for i in input().split()]
result = []

for i in range(0, n):
    badones = []
    for j in range(0, i):
        if abs(xcenters[j] - xcenters[i]) <= 2 * m:
            badones.append(j)
    if len(badones) == 0:
        result.append(m)
        continue

    maxheight = m
    for x in badones:
        temp = result[x] + sqrt((4 * m * m) - ((xcenters[x] - xcenters[i]) ** 2))
        if maxheight < temp:
            maxheight = temp
    result.append(maxheight)

print(*result)

from math import sqrt

s = str(input())
n, r = int(s.split(' ')[0]), float(s.split(' ')[1])
xs = str(input()).split(' ')
xs = [int(x) for x in xs]
locations = []

for x in xs:
	y = r
	for loc in locations:
		x2, y2 = loc
		if abs(x2 - x) <= 2 * r:
			y = max(y, y2 + sqrt(4 * r * r - abs(x2 - x) * abs(x2 - x)))
	locations.append((x, y))

for l in locations:
	print(str(l[1]), end=' ')

n, r = map(int, input().split())
x = list(map(int, input().split()))
y = [r] * n
for i in range(n):
    for j in range(i):
        if not (abs(x[i] - x[j]) > 2 * r):
            y[i] = max(y[i], (4 * r ** 2 - (x[i] - x[j]) ** 2) ** 0.5 + y[j])

for i in y:
    print(i, end=' ')

read = lambda: list(map(int, input().split()))
n, r = read()
x = list(read())
y = [0] * n
for i in range(n):
    cur = r
    for j in range(i):
        if 2 * r >= abs(x[i] - x[j]):
            cur = max(cur, y[j] + ((4 * r * r - (x[i] - x[j]) ** 2) ** 0.5))
    y[i] = cur
print(*y)


n, r = list(map(int, input().split()))
x = list(map(int, input().split()))

r2r4 = 4 * r**2 

y=[]
for i in range(0, n):
    max_y = r
    for j in range(i):
        if r2r4 >= (x[i] - x[j]) ** 2:
            max_y = max(max_y, y[j] + (r2r4 - (x[i]- x[j])**2)**0.5)
    y.append(max_y)    

print(*y)


import math
n, r = map(int, input().split())
x = list(map(int, input().split()))
y = [r]
for i in range(1, len(x)):
	cur = r
	for j in range(i):
		d = abs(x[i] - x[j])
		if d <= 2 * r:
			cur = max(cur, y[j] + math.sqrt(4 * r**2 - d**2))
	y.append(cur)
print(*y)

import bisect

n, r = input().split()
n, r = int(n), int(r)

disks = list(map(int, input().split()))

d = dict()

final = []

for x in disks:
    first = bisect.bisect_left(final, x - 2*r)
    last = bisect.bisect_right(final, x + 2*r)

    m = 0

    for i in range(first, last):
        loc = final[i]
        if (x - 2*r <= loc <= x + 2*r):
            m = max(m, (4*r**2 - (x - loc)**2)**0.5 + d[loc])

    d[x] = m
    print(m + r, end=' ')
    bisect.insort(final, x)


a=list(map(int, input().split(" ")))
y=list(map(int, input().split(" ")))
circ=[]
for i in range(a[0]):
    fy=a[1]
    for j in circ:
        delta=abs(y[i]-j[0])
        if delta<=2*a[1]:
            fy=max(fy,j[1]+((2*a[1])**2-delta**2)**.5)
    circ.append([y[i],fy])
for i in circ:
    print(i[1], end=" ")

n,r = map(int, input().split())
xs = list(map(int, input().split()))

import math
def ch(c1, c2):
    d = abs(c1[0] - c2[0])
    ph = math.sqrt(2*2*r*r - d*d)
    return c2[1]+ ph

cs = []
for i in range(len(xs)):
    h = r
    x = xs[i]
    for c in cs:
        if abs(x - c[0]) > 2*r:
            continue
        else:
            h = max(h, ch([x, h], c))
    cs.append([x, h])

print(' '.join([str(i[1]) for i in cs]))

from math import *

n, r = list(map(int, input().split()))
x = list(map(int, input().split()))
ans = []

for i in range(n):
    yi = r
    for j in range(i):
        if abs(x[j] - x[i]) <= 2 * r:
            yi = max(yi, ans[j] + sqrt(4 * r**2 - (x[j] - x[i])**2))
    ans.append(yi)
print(' '.join(map(str, ans)))


import math

def __starting_point():
  n, r = [int(x) for x in input().split()]
  x = [int(x) for x in input().split()]
  h = [None] * n
  for i in range(n):
    h[i] = r
    for j in range(i):
      if abs(x[i] - x[j]) <= 2 * r:
        h[i] = max(h[i], h[j] + math.sqrt(math.pow(2 * r, 2) - math.pow(x[i] - x[j], 2)))
  print(*h)

__starting_point()

import math
n,r=map(int,input().split())
v=[]
for i in list(map(int,input().split())):
    my=r+0
    for j in v:
        if j[0]<i and j[0]+r>=i-r or j[0]>=i and j[0]-r<=i+r:
            y=j[1]+math.sqrt(4*r*r-(j[0]-i)**2)
            if y>my:
                my=y
    v.append((i,my))
for i in v:
    print(i[1],end=' ')
    
    


import math


n,r=list(map(int,input().split()))
a=list(map(int,input().split()))



new=[r for i in range(n)]

for i in range(1,n):
    for j in range(i):
        temp=(2*r)**2 - (a[i]-a[j])**2        
        if(temp>=0):
            new[i]=max(new[i],math.sqrt(temp)+new[j])
print(*new)






from math import sqrt

n, r = [int(x) for x in input().split()]

xcoords = [int(x) for x in input().split()]
ycoords = [-1 for x in xcoords]

for i, disk in enumerate(xcoords):
    maxy = r
    for j, disk2 in enumerate(xcoords):
        if disk2 < disk - 2 * r or disk2 > disk + 2 * r or ycoords[j] == -1:
            continue

        y = sqrt(pow(2 * r, 2) - pow(abs(disk2 - disk), 2)) + ycoords[j]

        if y > maxy:
            maxy = y

    ycoords[i] = maxy

s = ""
for disk in ycoords:
    s += str(disk) + " "

print(s[:-1])



from math import sqrt

N, R = map(int, input().split())

disk_xs = map(int, input().split())

disks = []
for x in disk_xs:
    y = R
    for (x0, y0) in disks:
        sq = 4*(R**2) - (x0 - x)**2
        if sq >= 0:
            y1 = y0 + sqrt(sq)
            y = max(y, y1)

    disks.append((x, y))

print(' '.join(map(lambda x: str(x[1]), disks)))

import sys

#f = open('input', 'r')
f = sys.stdin
n, r = list(map(int, f.readline().split()))
xs = list(map(int, f.readline().split()))

import math

xy_before = []
ans = []
for x in xs:
  max_y = r
  for bx, by in xy_before:
    if abs(x - bx) <= 2*r:
      if max_y < by + math.sqrt((2*r)**2 - (x-bx)**2):
        max_y = by + math.sqrt((2*r)**2 - (x-bx)**2)
  ans.append(max_y)
  xy_before.append((x, max_y))

print(' '.join(map(str, ans)))


n,r=map(int,input().split())
x=list(map(int,input().split()))
y=[]
for i in range(n):
    s = []
    for j in range(i):
        if abs(x[i]-x[j]) < 2 * r + 0.0000001:
            s.append(j)
    max = r
    for j in s:
        if (4 * r * r - (x[i]-x[j])**2)**0.5 + y[j] > max:
            max = (4 * r * r - (x[i]-x[j])**2)**0.5 + y[j]
    y.append(max)
for i in y:
    print(i, end=' ')
            


import math


class Point:

    def __init__(self, x , y):
        self.x = x
        self.y = y


class Curling:

    def __init__(self, r):
        self.r = r
        self.r2 = r * r
        self.d = r * 2
        self.disks = []
        self.results = []

    def add(self, x):
        min_y = [self.r]
        for disk in self.disks:  # type: Point
            x_distance = abs(x - disk.x)
            if x_distance == 0:
                min_y.append(disk.y + self.d)
            elif x_distance == self.d:
                min_y.append(disk.y)
            elif x_distance < self.d:
                min_y.append(self.calc_min_y(disk, x))
        disk = Point(x, max(min_y))
        self.disks.append(disk)
        self.results.append(str(disk.y))

    def calc_min_y(self, disk: Point, x):
        cx = abs(disk.x - x) / 2
        dy = math.sqrt(self.r2 - cx * cx)
        return disk.y + 2 * dy


[n, r] = list(map(int, input().split()))
curling = Curling(r)
x_positions = list(map(int, input().split()))
for x_position in x_positions:
    curling.add(x_position)
print(" ".join(curling.results))


import math;
n, r = map(int, input().split());
X = list(map(int, input().split()));
C = [];
for q in range(len(X)):
    y = r;
    for w in range(len(C)):
        if abs(X[w] - X[q]) <= 2 * r:
            yc = math.sqrt(4 * r * r - (X[w] - X[q]) ** 2) +C[w];
            #print(yc);
            y = max(y, yc);
    C.append(y);
print(*C);

import math

n, r = map(int, input().split())

disk_list = map(int, input().split())

t = [-1 * r for i in range(1001)]

result = []
for disk in disk_list:

	start = disk - r * 2
	if start < 0:
		start = 0

	end = disk + r * 2
	if end > 1000:
		end = 1000

	max_y = 0
	for i in range(start, end + 1):

		x1 = i
		y1 = t[i]

		x2 = disk

		#Calculate y2
		y2 = math.sqrt(4 * (r**2) - (abs(x1 - x2) ** 2)) + y1


		if y2 > max_y:
			max_y = y2

	t[disk] = max_y
	result.append(max_y)

for i in result:
    print(i, end=" ")

#print(t[:10])