英雄无敌

Time Limit: 6000MS

Memory Limit: 65535KB

Description

英雄无敌是个很经典的游戏。Snow一直很好奇他的自动战斗功能是怎么实现的。

将问题简单化,现在规定

双方如果发生自动战斗,那么双方的士兵数是一样的。

A先手和b先手的概率都是0.5,之后轮流出手。

每次出手,随机的选取己方的一名士兵,随机攻击对方一名士兵,有一定概率杀死,否则攻击无效(即不会造成对方伤亡)。

请输出双方各自赢得比赛的概率。

Input

第一行是Case数

对于每个case

第一行是1个整数,0<n<=4,一方的士兵数

下面n行每行n个数,表示a的第i个士兵一次能杀死b的第j个士兵的概率。

下面n行每行n个数,表示b的第i个士兵一次能杀死a的第j个士兵的概率。

 

Output

返回2人赢得概率,保留6位小数。

Sample Input

1
1
0.5
0.5

Sample Output

0.500000 0.500000

Hint

None

Source

沈宇亮

提交代码