该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

$n$ 人住在坐标线上， $i$ /th人住在点 $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$ 人聚集到集合地点的时间最短。

Input

输入

第一行包含一个整数 $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}$ ) - 人的位置。( $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$ 。

Output

输出

对于每个测试用例，打印一个实数 - 最佳位置 $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

Note

注

• 在 $1$ -st 测试案例中，只有一个人，因此选择他或她的位置作为会面地点是有效的。然后，他或她将在 $3$ 分钟内到达，他或她需要穿好衣服。
• 在第 $2$ 个测试案例中，有 $2$ 个人不需要时间穿衣服。每个人都需要一分钟到达位置 $2$ 。
• 在 $5$ -th测试用例中， $1$ （第一个）人需要 $4$ 分钟到达位置 $1$ （ $4$ 分钟穿衣服， $0$ 分钟在路上）； $2$ （第二个）人需要 $2$ 分钟到达位置 $1$ （ $1$ 分钟穿衣服， $1$ 分钟在路上）。(穿衣服需要 $1$ 分钟，路上需要 $1$ 分钟）； $3$ 第 $4$ 个人需要 $4$ 分钟到达位置 $1$ 。(穿衣服需要 $2$ 分钟，路上需要 $2$ 分钟）。