E. Awesome Hack for Free GPA
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie's grades this year are... questionable.

The school year is divided into two semesters. Bessie's scores on assignments in each semester can be represented as integer sequences $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_m$$$ of length $$$n$$$ and $$$m$$$ respectively.

Bessie's grade for a semester is the average of all her scores in that semester. Her overall grade is the average of her semester grades. Here, the average of an integer sequence $$$x_1, x_2, \ldots, x_l$$$ of length $$$l$$$, is $$$\frac{x_1+x_2+\ldots+x_l}{l}$$$. Note that this value may not necessarily be integer.

Bessie has hacked into the school's computers, and can do the following operation at most $$$k$$$ times without raising suspicion:

  • Choose a single score from one of the semesters, and move it to the other.

At the end, both semesters should have at least one score. Help Bessie find the maximum overall grade she can achieve!

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^4$$$).

The first line of each test contains $$$n$$$, $$$m$$$, and $$$k$$$  — the number of scores in each semester, and the maximum number of operations ($$$1 \le n, m \le 10^5$$$, $$$0 \le k \le n+m$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, Bessie's scores in the first semester ($$$1 \le a_i \le 10^9$$$).

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$, Bessie's scores in the second semester ($$$1 \le b_i \le 10^9$$$).

It is guaranteed the sum of $$$n + m$$$ over all tests does not exceed $$$2 \cdot 10^5$$$.

Output

For each test, output a floating-point number, the maximum overall grade Bessie can achieve.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Scoring

In tests worth $$$50$$$ points, it is guaranteed that $$$1 \le n, m \le 100$$$.

Example
Input
3
2 5 0
6 1
1 1 1 1 1
2 5 1
6 1
1 1 1 1 1
6 9 4
9 2 15 1 13 11
10 3 4 7 5 8 6 14 12
Output
2.25
3.5
10.538461538461538
Note

In the first test, Bessie can't do anything. So her grade for the first semester is $$$\frac{6+1}{2}=3.5$$$, and her grade for the second semester is $$$\frac{1+1+1+1+1}{5} = 1$$$. Averaging these gives an overall grade of $$$\frac{1+3.5}{2}=2.25$$$.

In the second test, it is optimal to move the score of $$$1$$$ in the first semester to the second semester. Then, the averages for each semester become $$$6$$$ and $$$1$$$, resulting in an overall grade of $$$\frac{6+1}{2}=3.5$$$.