D. 随机数生成器
time limit per test
5 s
memory limit per test
512 megabytes
input
standard input
output
standard output
有一种随机数生成器工作原理如下：

它存储了若干个数据：一个正整数 $$$k$$$，以及 $$$n$$$ 个非负整数构成的数组 $$$a_1,a_2, \cdots, a_n$$$。

每次生成随机数时候，它先反复地在 $$$[1, n]$$$ 上等概率地随机生成整数，重复 $$$k$$$ 次，得到序列 $$$t_1, \dots, t_k$$$；随后计算 $$$l = \min{t_i}, r = \max{t_i}$$$，并返回 $$$\sum_{i = l}^{r}{a_i}$$$ 作为结果。

你喜欢很大的数。你心中有一个非负整数 $$$v$$$，如果随机数生成器返回的数大于等于 $$$v$$$，你就会很高兴。

经过一番友好交流，生成器的所有者允许你对内部数据进行修改。具体来说，你可以从数组 $$$a$$$ 的最前面删去连续零个或若干个数，再从最后面删去连续零个或若干个数，但不能将整个数组全部删完。随后将剩下的部分作为新的 $$$a$$$，其长度作为新的 $$$n$$$。

你需要寻找修改方案，使得返回的数大于等于 $$$v$$$ 的概率尽量大，输出这个最大概率。

Input

第一行输入正整数 $$$T$$$，表示数据组数。

对于每组数据，第一行输入三个整数 $$$n, k, v$$$，第二行输入 $$$n$$$ 个非负整数表示 $$$a_1, \dots, a_n$$$。保证 $$$1 \le n \le 3 \times 10^5, 1 \le k \le 5, 0 \le a_i, v \le 10^9$$$。

保证 $$$T$$$ 组数据的 $$$\sum{n} \le 3\times 10^5$$$。

Output

输出一个浮点数，表示最大概率。你需要保证绝对误差在 $$$10^{-8}$$$ 以内。

Example
Input
5
3 1 0
1 1 1
3 1 1
1 1 1
3 2 1
1 1 1
8 2 3
1 1 1 1 1 1 1 1
9 5 6
0 4 1 2 3 1 0 0 0
Output
1.000000000000
1.000000000000
1.000000000000
0.656250000000
0.967454037008