提示: 欢迎访问OurACM平台。
Problem 2149 Reverse Game

Accept: 82    Submit: 288    Special Judge
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

  Fat brother and Maze are playing a kind of special (hentai) game by N integers s1, s2… sn. Firstly Maze must arrange these n integers in a line, thus it makes an array S. Then Fat brother will randomly choose two indexes (l, r) with l < r and reverse interval S[l…r] (both inclusive). As Fat brother is such a boring guy, he will perform this action again and again for E times. After that, Fat brother and Maze will together randomly choose two indexes (l, r) with l < r and count the sum of interval S[l…r], let it be F. If F is large enough, Fat brother will be very happy and play a MORE special (hentai) game with Maze in the late night. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.) As Maze loves Fat brother so much, she wants to make the expected value of F as large as possible so that she would have a greater chance to play this kind of MORE special (hentai) game with Fat brother.

  Now she turns for your help, how to arrange these n integers to make the expected value of F as large as possible? For convenience, you just need to output the expected value of F under this arrangement.

Input

  The first line of the date is an integer T, which is the number of the text cases.

  Then T cases follow, each case contains two integers N and E description above.

  Then a line with N integers s1, s2… sn.

1 <= T <=100, 2 <=N<= 100, 1 <= E <=1000000086, 1 <= si <= 10086

Output

  For each case, output the expected value of F under your arrangement. See the sample input and output for more details.

Your answer will be accepted if your absolute error for each number is no more than 10-4.

Sample Input

4 2 0 1 2 2 1 1 2 3 0 1 2 3 10 10 1 2 3 4 5 6 7 8 9 10

Sample Output

3.000000 3.000000 5.000000 25.890449

Hint

This problem is special judge.

Submit  Back  Status  Discuss