There are $n$ players (numbered from 1 to $n$) playing PUBG (PlayerUnknown's Battlegrounds). The $i$-th player has an accuracy of $a_i$, which indicates the probability that he hits the target if he gives a shoot. As they are bored, they come up with an even more boring playing rule which is as follows:
In each round, the players shoot one by one in the order of player 1, player 2, ..., player $n$. Each player can shoot at most once in each round.
If one gets shot, he loses and quits the game immediately.
The game will continue until there is only one survivor, otherwise a new round begins.
By coincidence, every two people have different shooting accuracys. If you are smart enough, you may choose not to shoot anyone in some occasions. But these $n$ players are just simple-minded. If it's their turn, they are certain to shoot the person with the highest accuracy who still remains in the game (and the one with the highest accuracy will shoot the person with the second highest accuracy who still remains in the game).
It's your task to calculate the winning probability of each player.
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 200$), indicating the number of players.
The second line contains $n$ numbers $a_1, a_2, \dots, a_n$ ($0 < a_i < 1$), indicating the shooting accuracy of each player.
The distribution of $n$ in the test cases are listed as follows:
range of n | number of cases |
---|---|
(0, 20] | 9390 |
(20, 50] | 500 |
(50, 100] | 100 |
(100, 200] | 10 |
For each test case, output $n$ integers in one line, where the $i$-th integer indicates the winning probability of the $i$-th player.
Your answer will be considered correct if its absolute error or relative error is not larger than $10^{-6}$