Given $n$ and an integer sequence $a_0, a_1, \cdots, a_n$ of length $n+1$.

There is a piecewise function $f(x)$ with domain $[0, n]$, defined as follows:

• If $x$ is an integer, $f(x) = a_x$.
• Otherwise, let $k = \left\lfloor x \right\rfloor$, then $f(x) = a_k + (x - k)(a_{k+1} - a_k)$.

Now, two players, Min and Max, play a game. Before the game, both parties agree on a positive integer $A$ and a positive real number $\varepsilon$, and set the parameter $T = A$.

Subsequently, Max chooses a real number $x \in [0, n]$, and the game begins. Both players take turns modifying $x$, with Min going first, according to the following rules:

• If $T \le 0$, the game ends immediately.
• The current player chooses another real number $x'$ such that $x' \in [0, n]$ and $|x - x'| < T$.
• Update $x$ to $x'$, and update $T$ to $T - \varepsilon$.

Clearly, for any $\varepsilon > 0$, the game will end after a finite number of turns. Min wants to minimize the value of $f(x)$ after the game ends, while Max wants to maximize the value of $f(x)$ after the game ends. Let $R(A, \varepsilon)$ denote the final value of $f(x)$ given the parameters $A$ and $\varepsilon$ chosen beforehand. Given $A$, you need to calculate:

$$\lim_{\varepsilon \to 0^+} R(A, \varepsilon)$$

Input

Each test case may contain multiple test sets.

The first line of the input contains an integer $T$, representing the number of test cases.

For each test case:

The first line contains two integers $n, A$.

The next line contains $n+1$ integers $a_0, a_1, \cdots, a_n$.

Output

Output a single real number representing the answer. Your answer must be within an error of $10^{-4}$ from the correct answer.

Formally, if your output is $A_p$ and the correct answer is $A_j$, your answer is considered correct if and only if $\displaystyle \frac{|A_p - A_j|}{\max(1, |A_j|)} \le 10^{-4}$.

Examples

Input 1

2
3 1
11 -4 -5 14
6 4
2 5 4 6 -1 5 -10

Output 1

4.5
4.4705882352941176470588235294118

Note 1

For the first test case, the image of $f(x)$ is shown below.

The true answer is $\displaystyle\frac{9}{2}$.

For the second test case, the true answer is $\displaystyle \frac{76}{17}$.

Subtasks

For all data, $1 \le A \le n \le 10^5$, $1 \le \sum n \le 10^5$, $-10^6 \le a_i \le 10^6$.