N couple have been chosen for this year's Jhalak show. The judges are Remo D'Souza, Madhuri Dixit and Karan Johar. Each contestant is assigned some score by the judges immediately after their performance. Then they receive votes from their fans via sms or web. The point value given by judges and fans from all over india are then combined to get a final score.
Let S be the sum of the scores assigned by judges to all couples. Now lets take the case that a couple got J points from all the judges and F fraction of audience votes via sms and web. The total point of each couple would be J+S*F. Note that the sum of all fractions would be 1.
The couple with lowest score is eliminated.
Given the points couples got from judges, your task is to find out for each couple the minimum percentage of votes that the couple must receive in order to guarantee not to be eliminated, no matter how the rest of votes is distributed among other couples.
If the lowest score is shared by multiple couples no couple would be eliminated.
The first line of input starts with T, the number of test cases.Each test case begins with N, the number of couples followed by N integers s1, s2, s3, .... sN. Each of these si is the score received by the respective couple by the judges taken together.
N fractions as percentage with 6 digits after decimal. ith percentage being the minimum percentage of the votes for ith couple for not getting eliminated no matter how other couples get rest of the votes.
2 20 10
2 10 0
4 25 25 25 25
3 24 30 21
25.000000 25.000000 25.000000 25.000000
34.666667 26.666667 38.666667
Problem Setter: Dhruva Bhaswar