The Kingdom of Flea has $n$ cities, and the great King of Flea resides in the capital, which is city 1.

The biggest problem in the Kingdom of Flea is the water supply. Because there are so many fleas living in the capital, and the King compassionately shares his allocated water with the residents, the King often finds himself without water to drink.

Consequently, the Kingdom of Flea has built a cylindrical water tank in every city. These tanks are identical and sufficiently tall. After a rainy day, the $i$-th city has collected water to a height of $h_i$. Due to geographical and weather factors, the water heights collected by any two different cities are distinct.

The King has also enlisted the help of ant craftsmen to build a massive underground connection system. Each time the King uses the underground connection system, he can specify any number of cities and connect their water tanks using the system. After a sufficient amount of time, he closes the system. According to the principle of communicating vessels, the water in the tanks of these cities will reach the same height after this operation, and this height will be equal to the average of the heights of the specified water tanks.

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

Please tell the King: what is the maximum possible water level in the tank of the capital, city 1?

Input

The input file is drink.in.

The first line contains 3 positive integers $n, k, p$, representing the number of cities in the Kingdom of Flea, the maximum number of times the King can use the underground connection system, and the required precision of your answer. The meaning of $p$ is explained in the Output section.

The next line contains $n$ positive integers, describing the water levels in the 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 all $h_i$ are distinct, $1 \le h_i \le 10^5$.

Output

The output file is drink.out.

The output should contain a single real number, representing the maximum water level in the tank of city 1.

This real number can only contain a non-negative integer part, a decimal point, and a fractional part. The non-negative integer part is mandatory and should not have a sign. If there is a fractional part, the integer part and the fractional part are separated by a decimal point. If there is no fractional part, no decimal point should be added.

The real number you output must not have more than $2p$ digits after the decimal point; it is recommended to keep at least $p$ digits.

The data guarantees that the reference answer and the true answer have an absolute error of less than $10^{-2p}$.

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

In addition, you may receive partial points for each test case.

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

Examples

Input 1

3 1 3
1 4 3

Output 1

2.666667

Note 1

Since the system can be used at most once, there are 5 possible schemes: 1. Do not use the system: The water level in city 1 is 1. 2. Use the system once to connect cities 1 and 2: The water level in city 1 is $\frac{5}{2}$. 3. Use the system once to connect cities 1 and 3: The water level in city 1 is 2. 4. Use the system once to connect cities 2 and 3: The water level in city 1 is 1. 5. Use the system once to connect cities 1, 2, and 3: The water level in city 1 is $\frac{8}{3}$.

Input 2

3 2 3
1 4 3

Output 2

3.000000

Note 2

The optimal strategy here is to use the system twice: first connect cities 1 and 3, then connect cities 1 and 2.

Input 3

See drink/drink3.in and drink/drink3.ans in the contestant directory.

Note

To ensure the precision of the answer, we generally need to keep more than $p$ decimal places during the calculation process. We can prove that in the reference algorithms for each subtask, it is guaranteed that by always keeping $\frac{6}{5}p$ decimal places, the absolute error between the output for any input and the reference answer will be less than $10^{-p}$.

To facilitate the handling of high-precision decimals, we have provided a fixed-point high-precision decimal class. Contestants can refer to and use this class according to their needs, or they may choose not to use it. For specific usage, please refer to the provided document drink/decimal.pdf.

Please note that the final file you submit must be drink.cpp/c/pas; modifications to any other files will not be considered valid responses.

Subtasks