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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def isValid(mid):
	time = 0.0
	for i in range(n):
		if time < c[i]:
			time = c[i]
			time += mid
		elif time >= c[i] and time <= c[i] + d:
			time += mid
		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 > 1e-06:
		mid = (low + high) / 2
		if isValid(mid):
			ans = mid
			low = mid
		else:
			high = mid
	print('{0:.6f}'.format(ans))
	t -= 1


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-06
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 = 4000000000.0
	while high - low > e:
		mid = (low + high) / 2.0
		if valid(mid):
			low = mid
		else:
			high = mid
	print(mid)


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 > 1e-06:
		mid = low + (high - low) / 2
		if check(mid):
			ans = mid
			low = mid
		else:
			high = mid
	print('{0:.6f}'.format(ans))


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
		if isValid(arr, mid, n) == 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
	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


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, 2000000000.0)
	while low + 1e-06 < 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 > 5e-07:
		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 + 1e-06
		else:
			end = mid - 1e-06
	print(ans)


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()


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)


import sys
input = sys.stdin.readline
testcase = int(input())
e = 5e-07

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 = 2000000000.0
	precision = 1e-05
	for i in range(80):
		m = (l + r) / 2
		possible = True
		curr = 0
		for j in _list:
			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))