$n$ people live on the coordinate line, the $i$-th one lives at the point $x_i$ ($1 \le i \le n$). They want to choose a position $x_0$ to meet. The $i$-th person will spend $|x_i - x_0|$ minutes to get to the meeting place. Also, the $i$-th person needs $t_i$ minutes to get dressed, so in total he or she needs $t_i + |x_i - x_0|$ minutes.

Here $|y|$ denotes the absolute value of $y$.

These people ask you to find a position $x_0$ that minimizes the time in which all $n$ people can gather at the meeting place.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases. Then the test cases follow.

Each test case consists of three lines.

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of people.

The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^{8}$) — the positions of the people.

The third line contains $n$ integers $t_1, t_2, \dots, t_n$ ($0 \le t_i \le 10^{8}$), where $t_i$ is the time $i$-th person needs to get dressed.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single real number — the optimum position $x_0$. It can be shown that the optimal position $x_0$ is unique.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{−6}$. Formally, let your answer be $a$, the jury's answer be $b$. Your answer will be considered correct if $\frac{|a−b|}{max(1,|b|)} \le 10^{−6}$.


-----Examples-----

Input
7
1
0
3
2
3 1
0 0
2
1 4
0 0
3
1 2 3
0 0 0
3
1 2 3
4 1 2
3
3 3 3
5 3 3
6
5 4 7 2 10 4
3 2 5 1 4 6
Output
0
2
2.5
2
1
3
6


-----Note-----

In the $1$-st test case there is one person, so it is efficient to choose his or her position for the meeting place. Then he or she will get to it in $3$ minutes, that he or she need to get dressed.

In the $2$-nd test case there are $2$ people who don't need time to get dressed. Each of them needs one minute to get to position $2$.

In the $5$-th test case the $1$-st person needs $4$ minutes to get to position $1$ ($4$ minutes to get dressed and $0$ minutes on the way); the $2$-nd person needs $2$ minutes to get to position $1$ ($1$ minute to get dressed and $1$ minute on the way); the $3$-rd person needs $4$ minutes to get to position $1$ ($2$ minutes to get dressed and $2$ minutes on the way).

Difficulty: MEDIUM_HARD
Tags: Geometry

Sorting

Implementation

Greedy algorithms

Mathematics
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
tc = int(input())
for i in range(1, tc + 1):
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	a = [i + j for (i, j) in zip(x, t)]
	b = [i - j for (i, j) in zip(x, t)]
	ans = (max(a) + min(b)) / 2
	print(ans)


for (_, (xs, ts)) in ((input(), (tuple(map(int, input().split())) for _ in '00')) for _ in range(int(input()))):
	print((max((x + t for (x, t) in zip(xs, ts))) + min((x - t for (x, t) in zip(xs, ts)))) / 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [i + j for (i, j) in zip(a, b)]
	d = [i - j for (i, j) in zip(a, b)]
	print(0.5 * (max(c) + min(d)))


import sys
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	b = [*map(int, input().split())]
	print((max(map(lambda x: x[0] + x[1], zip(a, b))) + min(map(lambda x: x[0] - x[1], zip(a, b)))) / 2)


import collections

def do_test():
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	minx = min([x[i] - t[i] for i in range(n)])
	maxx = max([x[i] + t[i] for i in range(n)])
	print((maxx + minx) / 2)
t = int(input())
for _ in range(t):
	do_test()


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split(' ')))
	t = list(map(int, input().split(' ')))
	r = [a + b for (a, b) in zip(x, t)]
	l = [a - b for (a, b) in zip(x, t)]
	o = (max(r) + min(l)) / 2
	print(int(o) if o % 1 == 0 else o)


def segments_intersect(l1, r1, l2, r2):
	return l1 <= l2 <= r1 or l1 <= r2 <= r1 or l2 <= l1 <= r2 or (l2 <= r1 <= r2)

def all_intersect(lhs, rhs):
	ext_l = max(lhs)
	ext_r = min(rhs)
	if ext_l > ext_r:
		return False
	return all((segments_intersect(ext_l, ext_r, l, r) for (l, r) in zip(lhs, rhs)))

def solve():
	n = int(input())
	xx = list(map(int, input().split()))
	tt = list(map(int, input().split()))
	max_t = max(tt)
	lhs = [x - (max_t - t) for (x, t) in zip(xx, tt)]
	rhs = [x + (max_t - t) for (x, t) in zip(xx, tt)]
	if all_intersect(lhs, rhs):
		slowest_idx = next((i for (i, t) in enumerate(tt) if t == max_t))
		slowest_x = xx[slowest_idx]
		return slowest_x
	most_left = min(rhs)
	most_right = max(lhs)
	return (most_left + most_right) / 2
for test_id in range(int(input())):
	print(solve())


R = lambda : map(int, input().split())
(t,) = R()
exec(t * 'R();a=*zip(R(),R()),;print((max(x+y for x,y in a)+min(x-y for x,y in a))/2);')


t = int(input())

def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	t = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr += [lst[i] - t[i], lst[i] + t[i]]
	s = max(arr) + min(arr)
	if s % 2 == 0:
		print(s // 2)
	else:
		print(s // 2, end='')
		print('.', end='')
		print(5)
while t:
	solve()
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	left = a[0]
	right = a[-1]
	for i in range(n):
		if a[i] - b[i] < left:
			left = a[i] - b[i]
		if a[i] + b[i] > right:
			right = a[i] + b[i]
	ans = (left + right) / 2
	print(ans)
	t -= 1


n = int(input())
for i in range(n):
	x = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	min = l1[0] - l2[0]
	max = l1[0] + l2[0]
	for j in range(1, x):
		low = l1[j] - l2[j]
		high = l1[j] + l2[j]
		if low < min:
			min = low
		if high > max:
			max = high
	print((max + min) / 2.0)


for _ in range(int(input().strip())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	t1 = [l1[i] - l2[i] for i in range(n)]
	t2 = [l1[i] + l2[i] for i in range(n)]
	res = (min(t1) + max(t2)) / 2
	print(res)


from collections import defaultdict as dd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	x1 = [l[x] + l1[x] for x in range(n)]
	x2 = [l[x] - l1[x] for x in range(n)]
	print((max(x1) + min(x2)) / 2)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	mi = x[0] - t[0]
	ma = t[0] + x[0]
	for i in range(1, n):
		l = x[i] - t[i]
		h = x[i] + t[i]
		if l < mi:
			mi = l
		if h > ma:
			ma = h
	print((mi + ma) / 2.0)


def main():
	n_tests = int(input())
	for _ in range(n_tests):
		n = int(input())
		elems = list(map(int, input().split(' ')))
		times = list(map(int, input().split(' ')))
		updates = []
		for i in range(n):
			updates.append(elems[i] + times[i])
			updates.append(elems[i] - times[i])
		(min_v, max_v) = (updates[0], updates[0])
		for x in updates:
			if x > max_v:
				max_v = x
			if x < min_v:
				min_v = x
		print((max_v + min_v) / 2)
main()


K = int(input())
while K:
	k = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for (i, j) in zip(a, b):
		c.append(i - j)
		c.append(i + j)
	print((max(c) + min(c)) / 2)
	K -= 1


import math
import string
from typing import Optional

def mapped_read(cast):
	return map(cast, input().split())

def read_list(cast):
	return list(mapped_read(cast))

def lcm(a, b):
	return a // math.gcd(a, b) * b

def calc(x, t, a):
	return max([t[i] + abs(x[i] - a) for i in range(len(x))])

def solve():
	(n,) = mapped_read(int)
	x = read_list(int)
	t = read_list(int)
	a = [x[i] - t[i] for i in range(n)] + [x[i] + t[i] for i in range(n)]
	(l, r) = (min(a), max(a))
	print(f'{(l + r) / 2:.1f}')
n = 1
n = int(input())
for _ in range(n):
	solve()


from cmath import inf
t = int(input())
for _ in range(t):
	n = int(input())
	location = list(map(int, input().split(' ')))
	time = list(map(int, input().split(' ')))
	mins = []
	maxs = []
	max_time = max(time)
	index = -1
	is_find = False
	for i in range(n):
		remain_time = max_time - time[i]
		if remain_time == 0 and (not is_find):
			index = location[i]
			is_find = True
			continue
		mins.append(location[i] - remain_time)
		maxs.append(location[i] + remain_time)
	if len(mins) < 1:
		print(location[0])
		continue
	max_min = max(mins)
	min_max = min(maxs)
	if min_max < max_min:
		left = min([index, max_min, min_max])
		right = max([index, max_min, min_max])
		print((right + left) / 2)
	elif index < max_min:
		print((index + max_min) / 2)
	elif max_min <= index <= min_max:
		print(index)
	else:
		print((index + min_max) / 2)


for _ in range(int(input())):
	a = int(input())
	b = [int(i) for i in input().split()]
	c = [int(i) for i in input().split()]
	d = [c[i] + b[i] for i in range(a)]
	e = [b[i] - c[i] for i in range(a)]
	d.extend(e)
	(mi, ma) = (min(d), max(d))
	if (mi + ma) % 2 == 0:
		print((mi + ma) // 2)
	else:
		print((mi + ma) / 2)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	s = []
	f = 0.0
	for i in range(n):
		s.append(l1[i] + l2[i])
		s.append(l1[i] - l2[i])
	a = min(s) + max(s)
	f = a / 2
	print(f)


def meeting(arr1, arr2):
	k = 0
	index = arr1[0]
	for i in range(len(arr2)):
		if arr2[i] > k:
			k = arr2[i]
			index = arr1[i]
	pos = index
	left_side = 0
	right_side = 0
	for i in range(len(arr1)):
		if arr1[i] < pos:
			temp1 = pos - arr1[i] + arr2[i]
			left_side = max(left_side, temp1)
		elif arr1[i] > pos:
			temp2 = arr1[i] - pos + arr2[i]
			right_side = max(right_side, temp2)
	if left_side >= k and right_side >= k:
		opt_pos = index + (right_side - left_side) / 2
	elif left_side <= k and right_side <= k:
		opt_pos = index
	elif left_side <= k and right_side >= k:
		opt_pos = index + (right_side - k) / 2
	else:
		opt_pos = index - (left_side - k) / 2
	if opt_pos < 0:
		return 0
	else:
		return opt_pos
k = int(input())
for i in range(k):
	n = int(input())
	arr1 = input().split()
	arr1 = [int(l) for l in arr1]
	arr2 = input().split()
	arr2 = [int(l) for l in arr2]
	print(meeting(arr1, arr2))


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append(x[i] - t[i])
		a.append(x[i] + t[i])
	print((max(a) + min(a)) / 2)


from sys import stdin

def main():
	t = int(stdin.readline())
	for _ in range(t):
		n = int(stdin.readline())
		x = list(map(int, stdin.readline().split()))
		times = list(map(int, stdin.readline().split()))
		dic = {}
		m = -1
		m_idx = 0
		for i in range(n):
			if x[i] in dic:
				dic[x[i]] = max(dic[x[i]], times[i])
			else:
				dic[x[i]] = times[i]
			if m < times[i]:
				m = times[i]
				m_idx = x[i]
		min_pos = 1000000000
		max_pos = -1
		for set in dic.items():
			min_pos = min(min_pos, min(m_idx, set[0] + (m - set[1])))
			max_pos = max(max_pos, max(m_idx, set[0] - (m - set[1])))
		print((min_pos + max_pos) / 2)
main()


import sys
from os.path import exists
if exists('test.txt'):
	sys.stdin = open('test.txt', 'r')
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = list(map(int, input().split()))
	res = []
	for i in range(len(a)):
		res.append(a[i] - t[i])
		res.append(a[i] + t[i])
	print((max(res) + min(res)) / 2)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append(x[i] - t[i])
		arr.append(x[i] + t[i])
	ans = (max(arr) + min(arr)) / 2
	if int(ans) == ans:
		print(int(ans))
	else:
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	x = [int(x) for x in input().split()]
	t = [int(x) for x in input().split()]
	l = 100000000
	r = -100000000
	i = 0
	while i < n:
		if x[i] + t[i] > r:
			r = x[i] + t[i]
		if x[i] - t[i] < l:
			l = x[i] - t[i]
		i += 1
	print((l + r) / 2)


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def values():
	return tuple(map(int, sys.stdin.readline().split()))

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(sys.stdin.readline())

def instr():
	return sys.stdin.readline().strip()

def words():
	return [i for i in sys.stdin.readline().strip().split()]

def chars():
	return [i for i in sys.stdin.readline().strip()]

def solve():
	n = inp()
	d = values()
	t = values()
	(mn, mx) = (float('inf'), -float('inf'))
	for i in range(n):
		mn = min(mn, d[i] - t[i])
		mx = max(mx, d[i] + t[i])
	print((mn + mx) / 2)
for i in range(inp()):
	solve()
0


t = int(input())

def solve():
	n = int(input())
	x = [int(x) for x in input().split()]
	t = [int(x) for x in input().split()]
	tmax = max(t)
	xlower = 10 ** 9
	xupper = -1
	for i in range(n):
		if t[i] == tmax:
			if x[i] < xlower:
				xlower = x[i]
			if x[i] > xupper:
				xupper = x[i]
	mp = (xlower + xupper) / 2
	time_mp = tmax + (xupper - xlower) / 2
	leftmost = mp
	rightmost = mp
	for i in range(n):
		if x[i] < mp:
			rnge = time_mp - t[i]
			if x[i] + rnge < leftmost:
				leftmost = x[i] + rnge
		elif x[i] > mp:
			rnge = time_mp - t[i]
			if x[i] - rnge > rightmost:
				rightmost = x[i] - rnge
	print((leftmost + rightmost) / 2)
for _ in range(t):
	solve()


import sys
import math
t = int(input())
for i in range(t):
	n = int(input())
	positions = list(map(int, input().strip().split()))
	dressedTime = list(map(int, input().strip().split()))
	maxTime = max(dressedTime)
	left = []
	right = []
	for i in range(n):
		dist = maxTime - dressedTime[i]
		left.append(positions[i] - dist)
		right.append(positions[i] + dist)
	print((max(left) + min(right)) / 2)


t = int(input())
for i in range(t):
	n = int(input())
	x = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	l = []
	for j in range(n):
		l.append(x[j] - p[j])
		l.append(x[j] + p[j])
	ma = max(l)
	mi = min(l)
	print((ma + mi) / 2)


n = int(input())
for i in range(n):
	ppl = input()
	positions = list(map(int, input().split()))
	gettingready = list(map(int, input().split()))
	avg = (max(positions) + min(positions)) / 2
	new = []
	for i in range(len(positions)):
		new.append(positions[i] - gettingready[i])
		new.append(positions[i] + gettingready[i])
	new_avg = (max(new) + min(new)) / 2
	print(new_avg)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	if t.count(0) == len(t):
		print((max(x) + min(x)) / 2)
	else:
		a = []
		for i in range(n):
			a.append(x[i] - t[i])
			a.append(x[i] + t[i])
		print((max(a) + min(a)) / 2)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	l = []
	for e in range(n):
		l.append(x[e] + t[e])
		l.append(x[e] - t[e])
	print((max(l) + min(l)) / 2)


def main():
	for i in range(int(input())):
		test()

def test():
	n = int(input())
	x = list(map(int, input().split(' ')))
	t = list(map(int, input().split(' ')))
	mi = x[0] - t[0]
	ma = x[0] + t[0]
	for i in range(1, n):
		mi = min(x[i] - t[i], mi)
		ma = max(x[i] + t[i], ma)
	print((mi + ma) / 2)
main()


import sys
from itertools import accumulate
input = sys.stdin.readline

def find_max(t):
	m = 0
	ind = 0
	for (i, val) in enumerate(t):
		if val > m:
			m = val
			ind = i
	return (ind, m)
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	t = list(map(int, input().split()))
	(ind, m) = find_max(t)
	pi = p[ind]
	ls = [max(p[k] - (m - t[k]), pi) if p[k] >= pi else min(p[k] + (m - t[k]), pi) for k in range(n)]
	print((max(ls) + min(ls)) / 2)


def func():
	N = int(input())
	Pos = list(map(int, input().split()))
	Dressed = list(map(int, input().split()))
	max_pos = -999999999999
	min_pos = 999999999999
	for i in range(N):
		max_pos = max(max_pos, Pos[i] + Dressed[i])
		min_pos = min(min_pos, Pos[i] - Dressed[i])
	print((max_pos + min_pos) / 2)
n_tests = int(input())
for i in range(n_tests):
	func()


test = int(input())
for _ in range(test):
	input()
	l = 10000000000.0
	r = -10000000000.0
	index = [int(x) for x in input().split()]
	time = [int(x) for x in input().split()]
	for (i, j) in zip(index, time):
		l = min(l, i - j)
		r = max(r, i + j)
	print((l + r) / 2)


import sys
sys.setrecursionlimit(1000000)

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
for T in range(int(input())):
	n = ni()
	x = li()
	t = li()
	minn = min(x)
	maxx = max(x)
	for i in range(n):
		minn = min(minn, x[i] - t[i])
		maxx = max(maxx, x[i] + t[i])
	print((minn + maxx) / 2)


for i in range(int(input())):
	n = int(input())
	posi = list(map(int, input().split()))
	time = list(map(int, input().split()))
	(m1, m2) = (posi[0] - time[0], posi[0] + time[0])
	for i in range(n):
		m1 = min(m1, posi[i] - time[i])
		m2 = max(m2, posi[i] + time[i])
	print((m1 + m2) / 2)


s = int(input())
while s != 0:
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	mx = x[0] + t[0]
	mi = x[0] - t[0]
	for i in range(1, n):
		mi = min(mi, x[i] - t[i])
		mx = max(mx, x[i] + t[i])
	sum = mi + mx
	if sum % 2 == 0:
		print(sum // 2)
	else:
		print(str(sum // 2) + '.5')
	s -= 1


t = int(input())
output = []
for i in range(t):
	n = int(input())
	coordinates = [int(c) for c in input().split()]
	dress = [int(d) for d in input().split()]
	new_coordinates = []
	for j in range(n):
		if dress[j] != 0:
			new_coordinates.append(coordinates[j] - dress[j])
			new_coordinates.append(coordinates[j] + dress[j])
			n += 1
		else:
			new_coordinates.append(coordinates[j])
	output.append((max(new_coordinates) + min(new_coordinates)) / 2)
for o in output:
	print(o)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	ans = float('inf')
	ans1 = -float('inf')
	for i in range(n):
		ans = min(ans, l[i] - m[i])
		ans1 = max(ans1, l[i] + m[i])
	print((ans + ans1) / 2)


from math import fabs
t = int(input())
for i in range(t):
	n = int(input())
	line1 = input().split(' ')
	line2 = input().split(' ')
	intline = [int(x) for x in line1]
	intline2 = [int(x) for x in line2]
	x0 = intline[0]
	s0 = intline2[0]
	for j in range(1, len(intline)):
		x1 = intline[j]
		s1 = intline2[j]
		if x0 > x1:
			(x0, x1) = (x1, x0)
			(s0, s1) = (s1, s0)
		if x1 - x0 <= fabs(s1 - s0):
			if s1 > s0:
				x0 = x1
				s0 = s1
			else:
				pass
		else:
			x0 = (x1 + x0 + (s1 - s0)) / 2
			s0 = s1 + (x1 - x0)
	if x0 % 1 == 0.0:
		print(int(x0))
	else:
		print(x0)


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = int_arr()
	t = int_arr()
	mn = float('inf')
	mx = 0
	for i in range(n):
		mn = min(mn, a[i] - t[i])
		mx = max(mx, a[i] + t[i])
	ans = (mx + mn) / 2
	print(ans)


INT_MAX = 2147483627
import math
t = int(input())
cnt = 0
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	a = list(map(int, input().split()))
	maxx = -10 ** 9
	minn = 10 ** 9
	for i in range(n):
		maxx = max(maxx, l[i] + a[i])
		minn = min(minn, l[i] - a[i])
	print((maxx + minn) / 2.0)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	mx = a[0]
	mi = a[-1]
	for i in range(n):
		mx = max(mx, a[i] + b[i])
		mi = min(mi, a[i] - b[i])
	print(0.5 * (mx + mi))


cnt = int(input())
while cnt:
	n = int(input())
	x = list(map(int, input().split()))
	t = list(map(int, input().split()))
	(p, q) = (min(x), max(x))
	for i in range(n):
		p = min(p, x[i] - t[i])
		q = max(q, x[i] + t[i])
	print((p + q) / 2)
	cnt -= 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = list(map(int, input().split()))
	j = 0
	ma = -200000000
	mi = 200000000
	while j < n:
		ma = max(ma, a[j] + t[j])
		mi = min(mi, a[j] - t[j])
		j += 1
	print((ma + mi) / 2)


for _ in range(int(input())):
	n = int(input())
	arr = input().split(' ')
	time = input().split(' ')
	arr = [int(i) for i in arr]
	time = [int(i) for i in time]
	(a, b) = (-2 ** 31, -2 ** 31)
	for i in range(n):
		a = max(a, time[i] + arr[i])
		b = max(b, time[i] - arr[i])
	if (a - b) % 2:
		print((a - b) / 2)
	else:
		print((a - b) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	x_str = input()
	time_str = input()
	list_of_x_str = x_str.split(' ')
	x = [int(a) for a in list_of_x_str]
	list_of_time_str = time_str.split(' ')
	time = [int(a) for a in list_of_time_str]
	count = 0
	min_cor = 200000000
	max_cor = 0
	for i in range(n):
		count += 1
		min_cor = min(min_cor, x[i] - time[i])
		max_cor = max(max_cor, x[i] + time[i])
	print((min_cor + max_cor) / 2)


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	a = []
	b = []
	n = N()
	x = A()
	if 'dutrhg39fer89' == 32474864432759553:
		print('Tanmay')
	t = A()
	m = max(t)
	for i in range(n):
		dif = m - t[i]
		b.append(dif + x[i])
		a.append(max(0, x[i]) - dif)
	maxi = min(b)
	mini = max(a)
	print(int(maxi + mini) / 2)


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	aa = [float(i) for i in input().split()]
	t = [float(i) for i in input().split()]
	a = []
	for i in range(n):
		a.append(aa[i] + t[i])
		a.append(aa[i] - t[i])
	a.sort()
	print((a[0] + a[-1]) / 2)


nb_test = int(input())
ans = []
for _ in range(nb_test):
	n = int(input())
	xs = list(map(int, input().split(' ')))
	ts = list(map(int, input().split(' ')))
	best = 0
	worse_p = 0
	worse_n = 0

	def dist_p(i):
		return xs[i] + ts[i]

	def dist_n(i):
		return -xs[i] + ts[i]
	for i in range(n):
		if dist_p(i) >= dist_p(worse_p):
			worse_p = i
		if dist_n(i) >= dist_n(worse_n):
			worse_n = i
	an = (xs[worse_p] + xs[worse_n] + ts[worse_p] - ts[worse_n]) / 2
	if an.is_integer():
		an = int(an)
	ans.append(an)
for an in ans:
	print(an)


from math import inf
for _ in range(int(input())):
	n = int(input())
	coords = list(map(int, input().split()))
	time = list(map(int, input().split()))
	mx = time.index(max(time))
	x1 = inf
	x2 = -inf
	for i in range(n):
		if coords[i] <= coords[mx]:
			x1 = min(x1, min(coords[mx], coords[i] + (time[mx] - time[i])))
		if coords[i] >= coords[mx]:
			x2 = max(x2, max(coords[mx], coords[i] - (time[mx] - time[i])))
	print((x1 + x2) / 2)


for _ in range(int(input())):
	n = int(input())
	positions = [int(x) for x in input().split()]
	sorted_positions = sorted(positions)
	dressing_times = [int(x) for x in input().split()]
	max_dressing_time = -1
	index_of_maxes = []
	for (index, time) in enumerate(dressing_times):
		if time > max_dressing_time:
			index_of_maxes = [index]
			max_dressing_time = time
		elif time == max_dressing_time:
			index_of_maxes.append(index)
	first_element = sorted_positions[0]
	last_element = sorted_positions[-1]
	current_min_diff = 200000000.0
	centered_max_index = 0
	for index in index_of_maxes:
		pos = positions[index]
		diff = abs(abs(first_element - pos) - abs(last_element - pos))
		if diff < current_min_diff:
			centered_max_index = index
			current_min_diff = diff
	centered_pos = positions[centered_max_index]
	new_positions = []
	for i in range(n):
		time = dressing_times[i]
		pos = positions[i]
		max_time = time + abs(centered_pos - pos)
		if max_dressing_time > max_time:
			continue
		remaining_time = max_dressing_time - time
		new_positions.append(pos - remaining_time if centered_pos < pos else pos + remaining_time)
	sorted_positions = sorted(new_positions)
	print((sorted_positions[-1] + sorted_positions[0]) / 2)


ntestcases = int(input())
for t in range(ntestcases):
	numPeople = int(input())
	positions = list(map(int, input().split(' ')))
	dressingTimes = list(map(int, input().split(' ')))
	if dressingTimes[0] > 0:
		minPos = positions[0] - dressingTimes[0]
		maxPos = positions[0] + dressingTimes[0]
	else:
		minPos = positions[0]
		maxPos = positions[0]
	for i in range(1, numPeople):
		if dressingTimes[i] > 0:
			smol = positions[i] - dressingTimes[i]
			big = positions[i] + dressingTimes[i]
			minPos = min(minPos, smol)
			maxPos = max(maxPos, big)
		else:
			minPos = min(minPos, positions[i])
			maxPos = max(maxPos, positions[i])
	answer = (maxPos + minPos) / 2
	intAnswer = int(answer)
	if answer == intAnswer:
		print(intAnswer)
	else:
		print(answer)


from re import L
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	dis = inlt()
	time = inlt()
	k = 0
	ki = 0
	for i in range(n):
		if time[i] > k:
			k = time[i]
			ki = i
	mx = 1000000009
	mn = 0
	for i in range(n):
		mx = min(mx, dis[i] + abs(time[i] - k))
		mn = max(mn, dis[i] - abs(time[i] - k), 0)
	if mn <= mx:
		print(dis[ki])
	else:
		print((mx + mn) / 2)


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	times = [int(num) for num in input().split()]
	list2 = []
	for i in range(0, n):
		list2.append(list1[i] + times[i])
		list2.append(list1[i] - times[i])
	list2.sort()
	mid = (list2[0] + list2[-1]) / 2
	print(mid)


n = int(input())
z = []
for i in range(n):
	y = []
	x = int(input())
	p = input().split(' ')
	t = input().split(' ')
	for k in range(len(p)):
		y.append(int(p[k]) + int(t[k]))
		y.append(int(p[k]) - int(t[k]))
	min = 1000000000
	max = 0
	for i in range(len(y)):
		if y[i] > max:
			max = y[i]
		elif y[i] < min:
			min = y[i]
	print((max + min) / 2)
for a in range(len(z)):
	print(z[a])


t = int(input())
while t > 0:
	n = int(input())
	x = list(map(int, input().split(' ')))
	time = list(map(int, input().split(' ')))
	a = list()
	for i in range(n):
		a.append(x[i] + time[i])
		a.append(x[i] - time[i])
	minn = a[0]
	maxx = a[0]
	for v in a:
		minn = min(minn, v)
		maxx = max(maxx, v)
	summ = maxx + minn
	print(summ / 2)
	t -= 1


n = int(input())
for i in range(n):
	y = []
	x = int(input())
	p = input().split(' ')
	t = input().split(' ')
	for k in range(len(p)):
		y.append(int(p[k]) + int(t[k]))
		y.append(int(p[k]) - int(t[k]))
	y.sort()
	print((y[0] + y[-1]) / 2)


t = int(input())
for _ in range(t):
	n = int(input())
	(list_time, list_cord) = ([], [])
	list_cord = list(map(int, input().split()))
	list_time = list(map(int, input().split()))
	list_all_x_points = [0 for i in range(2 * n)]
	for i in range(0, 2 * n, 2):
		list_all_x_points[i] = list_cord[i // 2] + list_time[i // 2]
		list_all_x_points[1 + i] = list_cord[i // 2] - list_time[i // 2]
	maxi = mini = list_all_x_points[0]
	for i in list_all_x_points:
		maxi = max(maxi, i)
		mini = min(mini, i)
	sum = mini + maxi
	print(sum // 2, end='')
	if sum % 2:
		print('.5')
	else:
		print()


import collections
import sys
from typing import List
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from heapq import heappush, heappop
from itertools import accumulate
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
res = []
t = int(input())
for _ in range(t):
	n = int(input())
	(list_time, list_cord) = ([], [])
	list_cord = list(map(int, input().split()))
	list_time = list(map(int, input().split()))
	list_all_x_points = [0] * (2 * n)
	for i in range(0, 2 * n, 2):
		list_all_x_points[i] = list_cord[i // 2] + list_time[i // 2]
		list_all_x_points[1 + i] = list_cord[i // 2] - list_time[i // 2]
	maxi = mini = list_all_x_points[0]
	for i in list_all_x_points:
		maxi = max(maxi, i)
		mini = min(mini, i)
	sum = mini + maxi
	res.append(round(sum / 2, 1))
for i in res:
	print(i)


for i in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	tim = list(map(int, input().split()))
	cal = sorted(list(zip(tim, nums)), reverse=True)
	ans = [cal[0][0], cal[0][1]]
	for i in cal:
		if ans[1] < i[1]:
			if i[1] - ans[1] + i[0] > ans[0]:
				v = (i[1] - ans[1] + i[0] - ans[0]) / 2
				(ans[0], ans[1]) = (ans[0] + v, ans[1] + v)
		elif ans[1] > i[1]:
			if -i[1] + ans[1] + i[0] > ans[0]:
				v = (-i[1] + ans[1] + i[0] - ans[0]) / 2
				(ans[0], ans[1]) = (ans[0] + v, ans[1] - v)
	print(ans[1])


t = int(input())
for ncase in range(1, t + 1):
	n = int(input())
	x = [int(s) for s in input().split(' ')]
	t = [int(s) for s in input().split(' ')]
	z = [(x[i], x[i] - t[i], x[i] + t[i]) for i in range(n)]
	ans = 0
	z.sort()
	low = z[0][1]
	high = z[-1][2]
	for i in range(0, n):
		if z[i][1] < low:
			low = z[i][1]
		if z[i][2] > high:
			high = z[i][2]
	ans = (low + high) / 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	pos = [int(i) for i in input().split()]
	t_ex = [int(i) for i in input().split()]
	(pos, t_ex) = [list(x) for x in zip(*sorted(zip(pos, t_ex), key=lambda pair: pair[0]))]
	if n == 1:
		print(pos[0])
		continue
	left = [t_ex[0]]
	right = [t_ex[-1]]
	for i in range(1, len(pos)):
		left.append(max(t_ex[i], left[-1] + pos[i] - pos[i - 1]))
		right.append(max(t_ex[-i - 1], right[-1] + pos[-i] - pos[-i - 1]))
	right.reverse()
	if left[-1] <= right[-1]:
		print(pos[-1])
		continue
	for i in range(len(pos)):
		if left[i] >= right[i]:
			print(pos[i] + (right[i] - left[i]) / 2.0)
			break


import sys

def main():
	t = int(sys.stdin.readline()[:-1])
	for _ in range(t):
		n = int(sys.stdin.readline()[:-1])
		xs = list(map(int, sys.stdin.readline()[:-1].split()))
		ts = list(map(int, sys.stdin.readline()[:-1].split()))
		ids = list(range(len(xs)))
		ids.sort(key=lambda i: xs[i])
		(_xs, _ts) = ([], [])
		for i in ids:
			_xs.append(xs[i])
			_ts.append(ts[i])
		(xs, ts) = (_xs, _ts)
		d = []
		for i in range(len(xs)):
			if len(d) == 0:
				d.append(ts[i] - xs[i])
			else:
				d.append(max(d[-1], ts[i] - xs[i]))
		s = []
		for i in range(len(xs) - 1, -1, -1):
			if len(s) == 0:
				s.append(ts[i] + xs[i])
			else:
				s.append(max(s[-1], ts[i] + xs[i]))
		s = s[::-1]
		(_min, pos) = (float('inf'), -1)
		for i in range(len(xs)):
			cur = max(d[i] + xs[i], s[i] - xs[i])
			if cur < _min:
				(_min, pos) = (cur, xs[i])
			if i > 0:
				p = (s[i] - d[i - 1]) / 2
				if xs[i - 1] < p < xs[i]:
					cur = max(d[i - 1] + p, s[i] - p)
					if cur < _min:
						(_min, pos) = (cur, p)
		print(pos)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	time = list(map(int, input().split()))
	if len(x) == 1:
		print(x[0])
		continue
	st = sorted(list(zip(x, time)), key=lambda p: p[1])
	max_time = st[-1]
	time = list(map(lambda p: p - max_time[1], time))
	st = sorted(list(zip(x, time)), key=lambda p: p[0])
	most_left = None
	most_right = None
	for obj in st:
		left = obj[0] + obj[1]
		right = obj[0] - obj[1]
		mid = obj[0]
		if left <= max_time[0] <= right:
			if most_left is None:
				most_left = max_time[0]
			most_left = min(most_left, max_time[0])
			if most_right is None:
				most_right = max_time[0]
			most_right = max(most_right, max_time[0])
		else:
			if mid < max_time[0]:
				if most_left is None:
					most_left = right
				most_left = min(most_left, right)
			if mid > max_time[0]:
				if most_right is None:
					most_right = left
				most_right = max(most_right, left)
	print((most_left + most_right) / 2.0)


import sys, math
input = sys.stdin.readline
INF = int(1000000000.0) + 7

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [(a[i], b[i]) for i in range(n)]
	c.sort()
	pre = [0] * n
	suf = [0] * n
	for i in range(n):
		pre[i] = c[i][1] - c[i][0]
		suf[i] = c[i][0] + c[i][1]
	for i in range(1, n):
		pre[i] = max(pre[i], pre[i - 1])
	for i in range(n - 2, -1, -1):
		suf[i] = max(suf[i], suf[i + 1])
	ans = c[-1][0]
	ret = max(suf[-1] - c[-1][0], c[-1][0] + pre[-1])
	for i in range(n - 1):
		x = c[i][0] + pre[i]
		y = suf[i + 1] - c[i][0]
		if max(x, y) < ret:
			ret = max(x, y)
			ans = c[i][0]
		if y > x:
			z = (suf[i + 1] - pre[i]) / 2
			if c[i][0] <= z <= c[i + 1][0]:
				x = z + pre[i]
				y = suf[i + 1] - z
				if max(x, y) < ret:
					ret = max(x, y)
					ans = z
	print(ans)
t = 1
t = int(input())
for i in range(1, t + 1):
	solve()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	time = list(map(int, input().split()))
	x = []
	for i in range(n):
		x.append([arr[i], time[i]])
	x.sort()
	ans = 0
	mx = max(time)
	idx = -1
	md = 0
	for i in range(n):
		if x[i][1] == mx:
			idx = i
			md = x[i][0]
			break
	a = md
	b = md
	for i in range(n):
		if i < idx:
			x[i][0] += mx - x[i][1]
			x[i][0] = min(md, x[i][0])
			a = min(a, x[i][0])
		elif i > idx:
			x[i][0] -= mx - x[i][1]
			x[i][0] = max(md, x[i][0])
			b = max(b, x[i][0])
	ans = (b - a) / 2 + a
	if ans.is_integer():
		print(int(ans))
	else:
		print(ans)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(input())
	lstx = list(map(int, input().split()))
	lsty = list(map(int, input().split()))
	low = min(lstx)
	high = max(lstx)
	l = 0
	r = 200000001
	mid = (l + r) / 2
	ans = r
	while True:
		if r < l:
			break
		mid = (l + r) // 2
		lt = -1000000000000000.0
		rt = 1000000000000000.0
		er = 0
		for j in range(n):
			left = mid - lsty[j]
			if left < 0:
				er += 1
				break
			a = lstx[j] - left
			b = lstx[j] + left
			if a > r or b < l:
				er += 1
				break
			lt = max(lt, a)
			rt = min(rt, b)
		if er > 0:
			l = mid + 1
		else:
			ans = (lt + rt) / 2
			r = mid - 1
	if int(ans) == ans:
		ans = int(ans)
	print(ans)