Meeting on the Line

Description:

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}$$$.

Sample 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

Sample 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).