B. Собрание на прямой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$n$$$ людей живут на координатной прямой, $$$i$$$-й человек живет в точке $$$x_i$$$ ($$$1 \le i \le n$$$). Они хотят выбрать точку $$$x_0$$$ для встречи. $$$i$$$-й человек потратит $$$|x_i - x_0|$$$ минут, чтобы добраться до места встречи. Также $$$i$$$-му человеку требуется $$$t_i$$$ минут чтобы одеться, поэтому суммарно ему нужно $$$t_i + |x_i - x_0|$$$ минут чтобы добраться до места встречи.

Здесь $$$|y|$$$ обозначает модуль числа $$$y$$$.

Эти люди просят вас выбрать позицию $$$x_0$$$, которая минимизирует время, через которое все $$$n$$$ людей доберутся до места встречи.

Входные данные

В первой строке задано единственное целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Затем следуют сами наборы входных данных.

Каждый набор входных данных состоит из трех строк.

В первой строке задано единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество людей.

Во второй строке заданы $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le 10^{8}$$$) — позиции людей.

В третьей строке заданы $$$n$$$ целых чисел $$$t_1, t_2, \dots, t_n$$$ ($$$0 \le t_i \le 10^{8}$$$), где $$$t_i$$$ это время, которое нужно $$$i$$$-му человеку, чтобы одеться.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное вещественное число — оптимальная позиция $$$x_0$$$. Можно показать, что существует единственная оптимальная позиция $$$x_0$$$.

Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{−6}$$$. Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если $$$\frac{|a−b|}{max(1,|b|)} \le 10^{−6}$$$.

Пример
Входные данные
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
Выходные данные
0
2
2.5
2
1
3
6
Примечание
  • В $$$1$$$-м наборе входных данных есть только один человек, поэтому целесообразно выбрать место встречи в его позиции. Тогда он доберется до него за $$$3$$$ минуты, которые нужны ему, чтобы одеться.
  • Во $$$2$$$-м наборе входных данных есть $$$2$$$ человека, которым не нужно время, чтобы одеться. Чтобы добраться до позиции $$$2$$$, каждому из них потребуется по одной минуте.
  • В $$$5$$$-м наборе входных данных $$$1$$$-му человеку нужно $$$4$$$ минуты, чтобы добраться до позиции $$$1$$$ ($$$4$$$ минуты, чтобы одеться, и $$$0$$$ минут на сам путь); $$$2$$$-му человеку нужно $$$2$$$ минуты, чтобы добраться до позиции $$$1$$$ ($$$1$$$ минута, чтобы одеться, и $$$1$$$ минута на сам путь); $$$3$$$-му человеку нужно $$$4$$$ минуты, чтобы добраться до позиции $$$1$$$ ($$$2$$$ минуты, чтобы одеться, и $$$2$$$ минуты на сам путь).