Chef is the leader of Chef's Earth Defense Organization, and his mission is to counter aliens which are threatening the earth. According to information gathered by the organization, there are $N$ alien spaceships (numbered $1$ through $N$) planning to invade the earth. The $i$-th spaceship will appear on the radar at time $C_i$. Each spaceship needs $D$ time to reach earth once it appears on the radar. 
Chef's organization owns a huge laser cannon which can destroy one spaceship in one shot. However, once the cannon is used once it needs some amount of cool-down time in order to be used again (first shot doesn't require cool-down time before it is used). This cool-down time, however, is configurable. It has to be set before the first shot, and cannot be changed after that. If Chef sets a lower cool-down time, that would increase the energy consumed by the cannon, and vice-versa - the higher the cool-down time, the lower the energy consumed.
This might be a long battle, and Chef wants to use as little energy as possible. So Chef wants to maximize the cool-down time while still being able to destroy all spaceships before any of them arrive on earth. In particular, the $i$-th spaceship should be shot between the times $C_i$ and $C_i + D$ (both end points inclusive).

-----Input:-----
- The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two integers $N$ and $D$. 
- The second line contains $N$ space-separated integers $C_1, C_2, \ldots, C_N$.

-----Output:-----
For each test case, print a single line containing one real number― the maximum cool-down time possible. Your answer will be considered correct if the absolute or relative error of the answer does not exceed $10^{-6}$.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N \leq 10^5$
- $1 \leq C_i \leq 10^9$ for each valid $i$
- $1 \leq D \leq 10^9$
- The sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points): 
- $N \le 1,000$
- the sum of $N$ over all test cases does not exceed $10,000$
Subtask #2 (50 points): Original constraints

-----Sample Input:-----
2
3 2
3 2 3
2 1
5 6

-----Sample Output:-----
1.5000000000
2.0000000000

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
def isValid(mid):
 time = 0.0
 for i in range(n):
  if time < c[i]:
   time = c[i]
   time += mid # cannon cooling
  elif time >= c[i] and time <= c[i] + d:
   time += mid # cannon cooling
  else:
   return False
 return True

t = int(input())
while t != 0:
 n, d = list(map(int, input().split()))
 c = list(map(int, input().split()))[:n]
 ans = -1
 c.sort()
 low, high = 0, 10 ** 10
 while (high - low) > 0.000001:
  mid = (low + high) / 2
  if isValid(mid):
   ans = mid
   low = mid
  else:
   high = mid 
 print("{0:.6f}".format(ans))
 t -= 1


# cook your dish here
def valid(coolTime):
 Time = c[0]
 for i in range(1,n):
  if(Time+coolTime<c[i]):
   Time = c[i]
  elif(Time+coolTime<=c[i]+d):
   Time = Time + coolTime
  else:
   return False
 return True

e=1e-6
test=int(input())
for _ in range(test):
 l = input().split() 
 n = int(l[0])
 d = int(l[1])
 c = list(map(int, input().split()))
 c.sort()
 low = 0.0
 high = 4e9
 while(high-low>e):
  mid = (low+high)/2.0
  if(valid(mid)):
   low = mid
  else:
   high = mid
 print(mid)

# cook your dish here
def check(mid):
 time=0.0 
 for i in range(n):
  if time<=arr[i]:
   time=arr[i]+mid 
  elif time<=arr[i]+d:
   time+=mid 
  else:
   return False 
 return True 
 
for _ in range(int(input())):
 n,d=list(map(int,input().split()))
 arr=list(map(int,input().split()))
 arr.sort()
 low=0
 high=10000000000
 while ((high-low)>0.000001):
  mid=low+(high-low)/2 
  if check(mid):
   ans=mid 
   low=mid 
  else:
   high=mid
 print("{0:.6f}".format(ans)) 


# cook your dish here
def check(mid):
 time=0.0 
 for i in range(n):
  if time<arr[i]:
   time=arr[i]+mid 
  elif time<=arr[i]+d:
   time+=mid 
  else:
   return False 
 return True 
 
for _ in range(int(input())):
 n,d=list(map(int,input().split()))
 arr=list(map(int,input().split()))
 arr.sort()
 low=0
 high=10000000000
 while ((high-low)>0.000001):
  mid=low+(high-low)/2 
  if check(mid):
   ans=mid 
   low=mid 
  else:
   high=mid
 print("{0:.6f}".format(ans)) 


def valid(coolTime):
 Time = c[0]
 for i in range(1,n):
  if(Time+coolTime<c[i]):
   Time = c[i]
  elif(Time+coolTime<=c[i]+d):
   Time = Time + coolTime
  else:
   return False
 return True

e = 1e-6

t = int(input())

for lol in range(t):
 l = input().split() 
 n = int(l[0])
 d = int(l[1])
 c = list(map(int, input().split()))
 c.sort()
 low = 0.0
 high = 4e9
 while(high-low>e):
  mid = (low+high)/2.0
  if(valid(mid)):
   low = mid
  else:
   high = mid
 print(mid)

def isValid(arr,mid,n):
 t = 0.0
 for i in range(n):
  if t<arr[i]:
   t = arr[i] + mid
  elif t<=arr[i] + d:
   t = t + mid
  else:
   return False
 return True


for _ in range(int(input())):
 n,d = list(map(int,input().split(' ')))
 arr = [int(num) for num in input().split(' ')]
 duration = []
 ans = -1
 arr.sort()
  
 left = 0.0
 right = 10000000000
 while right -left >= 10**(-6):
  mid = (left+right)/2
  #print(mid)
  if isValid(arr,mid,n)==True:
   left = mid
   ans = mid
  else:
   right = mid
   
 print(ans)


def isValid(arr,mid):
 t = 0.0
 for i in range(len(arr)):
  if t<arr[i]:
   t = arr[i] + mid
  elif t<=arr[i] + d:
   t = t + mid
  else:
   return False
 return True


for _ in range(int(input())):
 n,d = list(map(int,input().split(' ')))
 arr = [int(num) for num in input().split(' ')]
 duration = []
 ans = -1
 arr.sort()
  
 left = 0.0
 right = 10000000000
 while right -left >= 10**(-6):
  mid = (left+right)/2
  #print(mid)
  if isValid(arr,mid)==True:
   left = mid
   ans = mid
  else:
   right = mid
   
 print(ans)


for _ in range(int(input())):
 n,d=map(int,input().split())
 c=list(map(int,input().split()))
 c.sort()
 left=0
 right=10**10
 pos=0
 while left<=right:
  con=0
  mid=(left+right)//2
  nxt=c[0]+mid
  for i in range(1,n):
   if nxt<c[i]:
    nxt=c[i]+mid
   elif nxt>=c[i] and nxt<=c[i]+d:
    nxt+=mid
   else:
    con=1
    break
  if con!=1:
   pos=mid
   left=mid+1
  else:
   right=mid-1
 left=0
 right=999999
 pos1=0
 #print(pos)
 while left<=right:
  con=0
  mid=(left+right)//2
  l=len(str(mid))
  b=['0']*(6-l)
  b+=[str(mid)]
  b=''.join(b)
  nxt1=str(pos)+'.'+b
  nxt1=float(nxt1)
  nxt=c[0]+nxt1
  for i in range(1,n):
   if nxt<c[i]:
    nxt=c[i]+nxt1
   elif nxt>=c[i] and nxt<=c[i]+d:
    nxt+=nxt1
   else:
    con=1
    break
  if con!=1:
   pos1=nxt1
   left=mid+1
  else:
   right=mid-1
 print(format(pos1,'.6f'))

import sys


def fn(a, mid, d):
 b = []
 for i in range(n):
  b.append(a[i] + d)
 t = 0.0
 for i in range(n):
  if(a[i] <= t and t <= b[i]):
   t += mid
  elif(t <= b[i]):
   t = (a[i] + mid)
  else:
   return False
 return True


t = int(input())
while t:
 n, d = list(map(int, sys.stdin.readline().split()))
 c = list(map(int, sys.stdin.readline().split()))
 c.sort()
 l = 0
 r = max(c)+d
 for i in range(100):
  mid = (l + r) / 2
  if(fn(c, mid, d)):
   l = mid
  else:
   r = mid
 print(mid)
 t -= 1


import sys


def fn(a, mid, d):
 b = []
 for i in range(n):
  b.append(a[i] + d)
 t = 0.0
 for i in range(n):
  if(a[i] <= t and t <= b[i]):
   t += mid
  elif(t <= b[i]):
   t = (a[i] + mid)
  else:
   return False
 return True


t = int(input())
while t:
 n, d = list(map(int, sys.stdin.readline().split()))
 c = list(map(int, sys.stdin.readline().split()))
 c.sort()
 l = 0
 r = 10**18
 for i in range(100):
  mid = (l + r) / 2
  if(fn(c, mid, d)):
   l = mid
  else:
   r = mid
 print(mid)
 t -= 1


from sys import stdin

readline = stdin.readline
results = []
for _ in range(int(readline())):
 n, d = list(map(int, readline().split()))
 c = sorted(map(int, readline().split()))
 low, high = 0.0, 2e9
 while low + 1e-6 < high:
  mid = 0.5 * (low + high)
  elapsed, okay = 0.0, True
  for start in c:
   if elapsed > start + d:
    okay = False
    break
   if elapsed < start:
    elapsed = start
   elapsed += mid
  if okay:
   low = mid
  else:
   high = mid
 results.append('{:.6f}'.format(low))
print('\n'.join(results))


t = int(input())
for _ in range(t):
 n, d = map(int, input().split())
 arr = list(map(int, input().split()))
 arr.sort()

 low, high = 0, arr[-1]+d
 while (high - low) > 0.0000005:
  mid = (high + low)/2
  time = arr[0] + mid
  ans = True
  for i in range(1, n):
   if arr[i] > time:
    time = arr[i]
    time += mid
   elif arr[i] <= time <= arr[i]+d:
    time += mid
   else:
    ans = False
    break
  if ans:
   low = mid
  else:
   high = mid

 print(low)

t= int(input())
for _ in range(t):
 n,d = map(int,input().split())
 c = list(map(int,input().split()))
 c.sort()
 start = 0
 end = 10**12
 possible = True
 ans = None
 while start<=end:
  mid = (start+end)//2
  current = c[0]
  for i in range(1,n):
   next = current + mid
   if next >= c[i] and next <= c[i] +d :
    current = next
    possible = True
   elif next < c[i]:
    current = c[i]
    possible = True
   else:
    possible = False
    break
  if possible:
   ans = mid
   start = mid + 1
  else:
   end = mid-1

 start = ans
 end = ans+1
 possible = True
 while start <= end:
  mid = (start + end) / 2
  current = c[0]
  for i in range(1, n):
   next = current + mid
   if next >= c[i] and next <= c[i] + d:
    current = next
    possible = True
   elif next < c[i]:
    current = c[i]
    possible = True
   else:
    possible = False
    break
  if possible:
   ans = mid
   start = mid + 0.000001
  else:
   end = mid - 0.000001


 print(ans)

t= int(input())
for _ in range(t):
 n,d = map(int,input().split())
 c = list(map(int,input().split()))
 c.sort()
 start = 0
 end = 10**12
 possible = True
 ans = None
 while start<=end:
  mid = (start+end)//2
  current = c[0]
  for i in range(1,n):
   next = current + mid
   if next >= c[i] and next <= c[i] +d :
    current = next
    possible = True
   elif next < c[i]:
    current = c[i]
    possible = True
   else:
    possible = False
    break
  if possible:
   ans = mid
   start = mid + 1
  else:
   end = mid-1

 start = ans
 end = ans+1
 possible = True
 while start <= end:
  mid = (start + end) / 2
  current = c[0]
  for i in range(1, n):
   next = current + mid
   if next >= c[i] and next <= c[i] + d:
    current = next
    possible = True
   elif next < c[i]:
    current = c[i]
    possible = True
   else:
    possible = False
    break
  if possible:
   ans = mid
   start = mid + 0.000001
  else:
   end = mid - 0.000001


 print(ans-0.0000001)

def binary_search(arr, x):
 arr.sort()
 low = 0
 high = len(arr) - 1
 mid = 0
 while low <= high:

  mid = low + (high-low)//2
  if arr[mid] < x:
   low = mid + 1
  elif arr[mid] > x:
   high = mid - 1
  else:
   return mid
 return -1
def ternary_search(l, r, key, ar):
 if (r >= l):
  mid1 = l + (r - l) // 3
  mid2 = r - (r - l) // 3
  if (ar[mid1] == key):
   return mid1
  if (ar[mid2] == key):
   return mid2
  if (key < ar[mid1]):
   return ternary_search(l, mid1 - 1, key, ar)
  elif (key > ar[mid2]):
   return ternary_search(mid2 + 1, r, key, ar)
  else:
   return ternary_search(mid1 + 1,
         mid2 - 1, key, ar)
 return -1
def cheaker(c,d,val,n):
 st = c[0]
 for i in range(1,n):
  if st+val < c[i]:
   st = c[i]
  elif st+val > c[i]+d:
   return False
  else:
   st += val
 return True

def binary_search_answer(low,high,d,a,n,de):
 x=1
 p=0
 while(p!=d):
  while((high - low )> x):
   mid = (high+low)/2
   if cheaker(a,de,mid,n):
    low= mid
   else:
    high = mid
  x/=10
  p+=1
 return low
def __starting_point():
 for i in range(int(input())):
  n,d= list(map(int,input().split()))
  a=[int(X) for X in input().split()]
  a.sort()
  print(binary_search_answer(0,2*(10**9),7,a,n,d))

__starting_point()

def binary_search(arr, x):
 arr.sort()
 low = 0
 high = len(arr) - 1
 mid = 0
 while low <= high:

  mid = low + (high-low)//2
  if arr[mid] < x:
   low = mid + 1
  elif arr[mid] > x:
   high = mid - 1
  else:
   return mid
 return -1
def ternary_search(l, r, key, ar):
 if (r >= l):
  mid1 = l + (r - l) // 3
  mid2 = r - (r - l) // 3
  if (ar[mid1] == key):
   return mid1
  if (ar[mid2] == key):
   return mid2
  if (key < ar[mid1]):
   return ternary_search(l, mid1 - 1, key, ar)
  elif (key > ar[mid2]):
   return ternary_search(mid2 + 1, r, key, ar)
  else:
   return ternary_search(mid1 + 1,
         mid2 - 1, key, ar)
 return -1
def cheaker(c,d,val,n):
 st = c[0]
 for i in range(1,n):
  if st+val < c[i]:
   st = c[i]
  elif st+val > c[i]+d:
   return False
  else:
   st += val
 return True

def binary_search_answer(low,high,d,a,n,de):
 x=1
 p=0
 while(p!=d):
  while((high - low )> x):
   mid = (high+low)/2
   if cheaker(a,de,mid,n):
    low= mid
   else:
    high = mid
  x/=10
  p+=1
 return low
def __starting_point():
 for i in range(int(input())):
  n,d= list(map(int,input().split()))
  a=[int(X) for X in input().split()]
  a.sort()
  print(round(binary_search_answer(0,2*(10**9),7,a,n,d),10))
# cook your dish here

__starting_point()

import sys

from sys import stdin
L,R=1,10**16
def ck(m):
 c=0
 for i,x in enumerate(l):
  if c<x:c=x
  if x+d<c:
   return False 
  c+=m
 return True
def bs():
  l,r=L,R
  while l<r:
   m=(l+r+1)//2
   if ck(m):
    l=m
   else:
    r=m-1
  return l
 
for _ in range(int(input())):
 n,d=map(int,input().split())
 d*=10**6
 l=sorted(map(lambda x: int(x)*(10**6),sys.stdin.readline().strip().split()))
 x=bs()
 print(x/10**6)



L,R=1,10**16
def ck(m):
 c=0
 for i,x in enumerate(l):
  if c<x:c=x
  if x+d<c:
   return False 
  c+=m
 return True
def bs():
  l,r=L,R
  while l<r:
   m=(l+r+1)//2
   if ck(m):
    l=m
   else:
    r=m-1
  return l
 
for _ in range(int(input())):
 n,d=map(int,input().split())
 d*=10**6
 l=sorted(map(lambda x: int(x)*(10**6),input().split()))
 x=bs()
 print(x/10**6)



L,R=1,10**16
def ck(m):
 c=0
 for i,x in enumerate(l):
  if c<x:c=x
  if x+d<c:
   return False 
  c+=m
 return True
def bs():
  l,r=L,R
  while l<r:
   m=(l+r+1)//2
   if ck(m):
    l=m
   else:
    r=m-1
  return l
 
for _ in range(int(input())):
 n,d=map(int,input().split())
 d*=10**6
 l=sorted(map(lambda x: int(x)*(10**6),input().split()))
 x=bs()
 print(x/10**6)

import sys
input = sys.stdin.readline
testcase = int(input())
e = 0.0000005

def check(m):
  curr = 0
  for i in range(n):
    if curr <= a[i]:
      curr = a[i] + m
    elif curr <= (a[i] + d):
      curr = curr + m
    else:
      return False
  return True

def bs(l, h):
  m = (l + h) / 2
  if check(m):
    if (m + e) <= h and check(m + e):
      return bs(m + e, h)
    else:
      return m
  else:
    return bs(l, m - e)

for _ in range(testcase):
  n, d = list(map(int, input().split()))
  a = list(map(int, input().split()))
  a.sort()
  print(bs(0, max(a) + d))

from sys import stdin

for _ in range(int(stdin.readline())):
 N,D = list(map(int,stdin.readline().split()))
 _list = list(map(int,stdin.readline().split()))

 _list.sort()

 l=0
 r=2e9
 precision=1e-5

 for i in range(80):
  m=(l+r)/2
  possible=True
  curr=0
  for j in _list:
   #print('curr={} m={} j={} possible={}'.format(curr,m,j,possible))
   if j>curr:
    curr=j
   if curr+precision>j+D:
    possible=0
    break
   curr+=m
  if possible:
   l=m
  else:
   r=m

 print(round(l,10))



from sys import stdin

for _ in range(int(stdin.readline())):
 N,D = list(map(int,stdin.readline().split()))
 _list = list(map(int,stdin.readline().split()))

 _list.sort()

 l=0
 r=2e9
 precision=1e-5

 for i in range(50):
  m=(l+r)/2
  possible=True
  curr=0

  for j in _list:
   #print('curr={} m={} j={} possible={}'.format(curr,m,j,possible))
   if j>curr:
    curr=j
   if curr+precision>j+D:
    possible=0
    break
   curr+=m
  if possible:
   l=m
  else:
   r=m

 print(round(l,10))



from sys import stdin

for _ in range(int(stdin.readline())):
 N,D = list(map(int,stdin.readline().split()))
 _list = list(map(int,stdin.readline().split()))

 _list.sort()

 l=0
 r=2e9
 precision=1e-5

 for i in range(70):
  m=(l+r)/2
  possible=True
  curr=0

  for j in _list:
   #print('curr={} m={} j={} possible={}'.format(curr,m,j,possible))
   if j>curr:
    curr=j
   if curr+precision>j+D:
    possible=0
    break
   curr+=m
  if possible:
   l=m
  else:
   r=m

 print(round(l,10))