There are $$$n$$$ trees along a road. The height of the $$$i$$$-th tree is $$$a_i$$$.
In one operation, you can select a tree with positive height and cut it one unit of wood. You must perform exactly $$$s$$$ operations.
After $$$s$$$ operations, consider the set of trees with positive height. You need to output the minimum possible $$$\text{variance}^{\dagger}$$$ of the heights of these remaining trees.
$$$^{\dagger}$$$ The $$$\text{variance}$$$ of a sequence $$$b_1, b_2, \ldots, b_k$$$ is defined as:
$$$$$$ \text{variance} = \frac{1}{k} \sum_{i=1}^{k} (b_i - \overline{b})^2 $$$$$$
where $$$\overline{b}$$$ is the average of the sequence, s.t. $$$\overline{b} = \frac{b_1 + b_2 + \dots + b_k}{k}$$$.
For example, for the sequence $$$\{3,5,1,4,2\}$$$:
$$$$$$ \overline{b} = 3, \quad \text{variance} = \frac{1}{5}((3-3)^2 + (5-3)^2 + (1-3)^2 + (4-3)^2 + (2-3)^2) = 2. $$$$$$
There are multiple test cases. The first line of the input contains one integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, denoting the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$s$$$ $$$(1 \leq n \leq 2 \times 10^5, 1 \leq s \leq 10^9)$$$, denoting the number of trees and the number of units of wood you must cut.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^6)$$$, denoting the initial heights of the trees.
It's guaranteed that $$$s \lt \sum a_i$$$, so there will always be at least one tree with positive height after all cuts, and it's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times10^5$$$.
For each test case, output one real number in one line, denoting the minimal possible variance of the remaining trees' heights after the cuts.
Your answer will be considered correct if it has an absolute or relative error not exceeding $$$10^{-4}$$$. Formally, suppose that your answer is $$$a$$$ and the jury's answer is $$$b$$$, your answer is accepted if and only if $$$\frac{\left| a - b \right|}{\max(1, |b|)} \le 10^{-4}$$$.
25 31 2 3 4 53 125 6 7
0.500000 0.000000
For the first test case, one optimal strategy is to cut tree 1 once and tree 5 twice. The remaining trees have heights $$$\{2,3,4,3\}$$$, and their variance is $$$0.5$$$.
For the second test case, one optimal strategy is to cut tree 1 five times and tree 3 seven times. The remaining trees have heights $$$\{6\}$$$, and the variance is $$$0$$$.
It can be proved that no other strategy yields a smaller variance.
