Problem Description

In the Flea Kingdom, there are $n$ cities. The great Flea King resides in the capital city, which is the city number $1$.

The biggest issue in the Flea Kingdom is the water supply problem. Due to the high population in the capital, the Flea King generously shares the water allocated to him with the citizens, which often leaves him without water.

To address this, the Flea Kingdom has built cylindrical water tanks in every city. These tanks are identical and sufficiently tall. After a rainy day, the $i$-th city collects water to a height of $h_i$. Due to geographical and weather factors, the water heights collected in different cities are unique.

The Flea King has also hired ant craftsmen to build a vast underground connecting system. Each time the Flea King uses this system, he can select any number of cities and connect their water tanks through the system for a sufficiently long time, after which the system is closed. By the principle of communicating vessels, the water levels in these cities' tanks will reach the same height, which is the average of the selected tanks' heights.

Due to the complexity of the underground system, the Flea King can use it at most $k$ times.

The Flea King asks you to determine the maximum possible water level in the capital city's tank.

Input Format

The first line of input contains three positive integers $n$, $k$, and $p$, representing the number of cities in the Flea Kingdom, the maximum number of times the Flea King can use the underground connecting system, and the required precision of your output, respectively. The meaning of $p$ will be explained in the Output Format.

The next line contains $n$ positive integers, describing the water levels in the cities' tanks after the rain. The $i$-th positive integer $h_i$ represents the water level in the $i$-th city's tank. It is guaranteed that $h_i$ are unique and $1 \leq h_i \leq 10^5$.

Output Format

Output a single real number, representing the maximum water level in the capital city's tank.

This real number should only include the non-negative integer part, the decimal point, and the decimal part. The non-negative integer part is mandatory and should not have a sign. If there is a decimal part, it should be separated from the integer part by a decimal point. If there is no decimal part, do not include the decimal point.

Your output should not have more than $2p$ digits after the decimal point, and it is recommended to keep at least $p$ digits. The data guarantees that the absolute error between the reference answer and the true answer is less than $10^{-2p}$.

Your output is considered correct if and only if the absolute error between your output and the reference answer is less than $10^{-p}$.

If the absolute error between your output and the reference answer is not less than $10^{-p}$ but less than $10^{-5}$, you can earn $40\%$ of the points for that test case.

Sample Input and Output

Input Sample #1

3 1 3
1 4 3

Output Sample #1

2.666667

Input Sample #2

3 2 3
1 4 3

Output Sample #2

3.000000

Notes/Hints

Sample Explanation 1

Since the Flea King can use the underground connecting system at most once, there are five possible plans:

1. Do not use the underground connecting system: The water level in the capital city's tank is $1$.
2. Use the system once, connecting cities $1$ and $2$: The water level in the capital city's tank is $5/2$.
3. Use the system once, connecting cities $1$ and $3$: The water level in the capital city's tank is $2$.
4. Use the system once, connecting cities $2$ and $3$: The water level in the capital city's tank is $1$.
5. Use the system once, connecting cities $1$, $2$, and $3$: The water level in the capital city's tank is $8/3$.

Sample Explanation 2

The optimal plan here is to use the system twice, first connecting cities $1$ and $3$, then connecting cities $1$ and $2$.

Data Range

见题面 Input 部分

见题面 Output 部分