提示: 欢迎访问OurACM平台。
Problem 2145 Rock-Paper-Scissors Game

Accept: 17    Submit: 64    Special Judge
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Fat brother and Maze are playing a kind of special (hentai) rock-paper-scissors game with N friends in the house (so totally N+2 people). At each turn, each player plays Rock, Paper or Scissors by their hands at the same time. Rock defeats scissors, scissors defeats paper and paper defeats rock. If everyone play the same item or all the three items (rock, paper and scissors) show up, the game is tied. Otherwise, the one who lose in this turn will leave the house and play a MORE special (hentai) game outside. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.) And the rest of them will go into the next turn. The game ends until there is only one guy left in the house.

As Fat brother loves Maze very much, he doesn’t want Maze left the house. (pure evil guy, you know why) So before this special (hentai) game, he investigate all the other people (include Maze) and knows the probability they will play rock, paper, scissors during the game. So he decides to try him best to let Maze win. You can assume that this probability would never change. Now your task is to calculate the probability that Maze can win while Fat brother choose his best strategy and ALL other people play randomly. Note that Fat brother wants Maze win, not himself.

Input

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

Then T cases follow, each an integer N described above.

Then a line with three decimal numbers describe the probability that Maze will play rock, paper, scissors during the game

Then N lines follow, the ith line contains three decimal numbers which descript the probability that the ith friend will play rock, paper, and scissors during the game.

1 <= T <= 100, 1 <= N <= 15.

In 99% of the test cases, 1 <= N <= 10.

Each probability is larger than 0.1 with at most 2 digits after decimal point.

Output

For each case, output the probability that Maze can win while Fat brother choose his best strategy and ALL other people play randomly.

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

Sample Input

2 0 0.2 0.2 0.6 1 0.2 0.2 0.6 0.3 0.3 0.4

Sample Output

0.750000000000 0.507352941176

Hint

One of the games may goes as follow:

Turn 1 and Turn 4 are ties, the one who plays rock all the time (Doraemon) wins this special (hentai) game.

This problem is special judge.


Submit  Back  Status  Discuss