题目描述

决策和计策是神犇。

又到了吔饭的时间，可是决策和计策没有时间去吔饭，于是他们决定选出一个人去带饭。

计策提议使用石头剪刀布决出胜负，但是决策觉得这样太没有技术含量，不能做出很有趣的决策，他提出了用这样一种小游戏决定胜负：

____1.双方各有一个能量槽，可以存储 $0$ 到 $n$ 的能量值，当能量槽满了的时候可以释放大招，消耗所有能量并秒杀一切技能。（假如两个人都放大招则游戏继续）

____2.除了大招之外有 $m$ 个小技能，小技能有 $3$ 类：

________(1):消耗型，消耗 $x$个能量，只有能量不小于 $x$ 时才能使用。

________(2):免费型，不消耗能量，任何时候都可以使用。

________(3):补给型，使用后能获得 $x$ 个能量，但是获得后最多只能有 $n$ 个能量（多出来部分的会浪费掉），任何时候都可以使用。

____3.小技能之间有相克的关系，当然也有不相互影响的小技能对。

____4.每回合每个人必须选择一种可行技能，然后同时亮出。假如这两个技能相克，则某一方立即获得胜利。

否则双方更新自己的能量然后继续游戏。

____注意：假如游戏永远都不会结束算作平局，即双方各加 $0.5$ 胜场，所以双方胜率之和一定为 $1$。

决策发现自己可以用AI跟计策打一局，这样就不用每次自己去花力气打了。

决策还发现每个状态的最优策略是固定的，所以自己只需要给程序一张决策表，告诉它在每个状态有多少概率出某个决策就行了。

但是计策很有计策，决策知道计策会偷偷潜入他的电脑偷看他的程序和决策表。但是由于决策使用了 $time$ 作为随机种子，所以计策并不能知道这一次到底会出什么，只知道每种决策的出现概率。

现在决策找到了你，请你找出一种方案使得自己的胜率不低于 $50\%$。

但同时计策也找到了你，他给了你决策的决策表，请你找出一种方案使得胜率最大。

与此同时鏼也找到了你，他给出了两个人的决策表，想请你算出每个人有多少的胜率。

注意：很明显假如有人能量槽满了的话他一定会放大招，所以决策表只有 $n\times n$ 种局面。

决策表输入输出格式

共 $n\times n$ 行，第 $i$ 行（从 $0$ 开始计数）表示己方能量为 $i\div n$，对方能量为 $i\bmod n$ 时的决策。

每个决策占一行，首先第一个数 $x$ 表示该状态可行的决策数，接下来 $x$ 个自然数分别表示将可行决策按编号从小到大排序后每个决策的出招概率$\times 10^9$，并且这 $x$ 个数之和为 $10^9$。

输入格式

多组数据。第一行为测试点编号，数据组数 $Case$ 和数据类型 $type$。

对于每一组数据：

____第一行两个整数分别表示大招的能量消耗 $n$ 和小招的种类数 $m$。

____若 $type=1$ 则你需要解决鏼的询问，若 $type=2$ 则你需要解决计策的询问，若 $type=3$ 则你需要解决决策的询问。

____接下来一行 $m$ 个数 $v_i$ 分别表示小招的损耗。$v_i<0$ 表示消耗型，$v_i=0$ 表示免费型，$v_i>0$ 表示补给型（即使用后能量会加上 $v_i$）。

____接下来 $m$ 行每行 $m$ 个数，如果为 $1$ 表示所在行的技能克制所在列的技能，如果为 $-1$ 表示所在列的技能克制所在行的技能，如果为 $0$ 表示没有克制关系。保证该矩阵对称且对角线上是 $0$。

____假如 $type!=3$，接下来 $n\times n$ 行为决策的决策表。

____假如 $type==1$，接下来 $n\times n$ 行为计策的决策表。

输出格式

如果 $type=1$，输出一行一个浮点数表示决策的胜率。（和标准答案误差在1e-6之内均算作正确）。

如果 $type=2$，输出一个决策表，设该决策表对决策的决策的胜率为x，我们提供的参考解胜率为 $y$，那么当 $x>y-10^{-6}$ 时算作正确。

如果 $type=3$，输出一个决策表，我们会生成一个决策表，设你的决策表对我们的决策表的胜率为 $x$，那么当 $x>0.5-10^{-6}$ 时算作正确。

注：spj为了防止精度误差，在假如某个状态只有低于 $10^{-8}$ 的概率转移出死循环时直接将该状态胜率置为 $0.5$。

0 1 1
2 3
-1 0 1
0 0 1
0 0 0
-1 0 0
2 0 1000000000
2 1000000000 0
3 0 0 1000000000
3 333333334 333333333 333333333
2 0 1000000000
2 1000000000 0
3 0 0 1000000000
3 333333334 333333333 333333333

0.5000000000

提示

除了第 5,6 两个点，其他点数据均为随机生成。

游戏生成方式：

____对于每个技能，有 $1/3$ 的概率是免费型，$1/3$ 是消耗型，$1/3$ 是补给型，且消耗型和补给型的 $x$ 的绝对值不超过 $3$。

____保证三种技能至少都有一个。

____克制矩阵生成方式：对于每一对技能，有 $80$ 的概率没有关系，否则：

________假如使用后能量损失相同则各有 $50$ 概率克制对方。

________假如使用后不同则收益大的一方有 $20$ 的概率克制对方，收益小的一方有 $80$ 的概率克制对方。

____保证每个补给型技能至少被一个技能克制。

____保证至少存在一个补给型技能使得只有消耗型技能才能克制它。

决策表生成方式：

____首先将每个状态可行决策使用概率置为相等（任意两个之差不超过 $1$）。

____然后进行 $100$ 次操作，每次操作选择两个不同的技能，将A技能减少为(1~A技能原来概率)之间的随机数，B技能加上相应概率。

数据范围

对于 $100\%$ 的数据，$N\le 5,M\le 30,Type\le 3$。