决策和计策是神犇。
又到了吔饭的时间，可是决策和计策没有时间去吔饭，于是他们决定选出一个人去带饭。
计策提议使用石头剪刀布决出胜负，但是决策觉得这样太没有技术含量，不能做出很有趣的决策，他提出了用这样一种小游戏决定胜负：
- 双方各有一个能量槽，可以存储至多 $n$ 点能量。
- 双方都有大技能，当能量槽满了的时候可以释放大技能，并消耗所有能量。
- 除了大技能之外有 $m$ 种小技能，编号为 $1, \dots, m$，分为三类：
- 消耗型，消耗 $x$ 个能量，只有能量不小于 $x$ 时才能使用。
- 免费型，不消耗能量，任何时候都可以使用。
- 补给型，使用后能获得 $x$ 个能量，但是使用后总能量如果超过 $n$ 点那么多余部分会被浪费掉。任何时候都可以使用。
- 消耗型，消耗 $x$ 个能量，只有能量不小于 $x$ 时才能使用。
- 技能之间有一些相克的关系。大技能克所有小技能。游戏规定了小技能间有若干个相克关系，每个关系形如：$i$ 号小技能克 $j$ 号小技能。其它技能之间没有相克关系。
- 每回合每个人必须选择一种可使用的技能，然后同时亮出。假如一方出的技能克对方出的技能，那么游戏结束该方获胜。否则双方更新自己的能量槽然后继续游戏。当然，如果同时出大技能那么双方都会清空能量槽然后继续游戏。
- 如果游戏永远都不会结束那么算作双方各赢 $0.5$ 场。
决策发现自己可以用 AI 跟计策打一局，这样就不用每次自己去花力气打了。
决策还发现每个游戏局面的最优策略只跟双方的能量槽有关，所以自己只需要给程序一张策略表，上面记录了每个状态下出每种技能的概率分别是多少就行了。
但是计策很有计策，决策知道计策会偷偷潜入他的电脑偷看他的程序和策略表。但是由于决策使用了当前系统时间作为随机种子，所以计策并不能知道这一次到底会出什么，只知道出每种技能的概率。
现在决策找到了你，请你找出一种方案使得自己的胜率不低于 $50\%$。
但同时计策也找到了你，他给了你决策的策略表，请你找出一种方案使得胜率最大。
与此同时鏼也找到了你，他给出了两个人的策略表，想请你算出每个人有多少的胜率。
策略表的输入输出格式
每个能量槽有 $n + 1$ 种状态，所以游戏局面共 $(n + 1)^2$ 种。很明显假如有人能量槽满了的话他一定会放大技能，所以策略表只用记录 $n^2$ 种局面的策略。
共 $n^2$ 行，第 $i$ 行（从 $0$ 开始编号）表示己方能量为 $\lfloor \frac{i}{n} \rfloor$，对方能量为 $i \bmod n$ 时的策略。
每个策略占一行，共 $m$ 个整数，分别表示使用小技能 $1, \dots, m$ 的概率乘以 $10^9$ 后的结果。保证这些数加起来为 $10^9$，保证当前不可使用的小技能的使用概率为 $0$（即某些消耗型）。
输入格式
多组数据。第一行为测试点编号，数据组数 $\mathrm{Case}$ 和数据类型 $\mathrm{type}$。
对于每一组数据，第一行两个正整数分别表示能量槽上限 $n$ 和小技能种类数 $m$。
若 $\mathrm{type}=1$ 则你需要解决鏼的询问，若 $\mathrm{type}=2$ 则你需要解决计策的询问，若 $\mathrm{type}=3$ 则你需要解决决策的询问。
接下来一行 $m$ 个整数 $v_1, \dots, v_m$ 分别表示小技能对能量槽的改变量，即使用后使用者的能量会加上 $v_i$。$v_i \lt 0$ 表示消耗型，$v_i = 0$ 表示免费型，$v_i>0$ 表示补给型。
接下来 $m$ 行每行 $m$ 个数，第 $i$ 行第 $j$ 列如果为 $1$ 表示 $i$ 号小技能克 $j$ 号小技能，如果为 $-1$ 表示 $j$ 号小技能克 $i$ 号小技能，如果为 $0$ 表示没有相克关系。保证对角线上元素均为 $0$ 且第 $i$ 行第 $j$ 列的元素等于第 $j$ 行第 $i$ 列的元素的相反数。
假如 $\mathrm{type} \neq 3$，接下来 $n^2$ 行为决策的策略表
假如 $\mathrm{type} = 1$，接下来 $n^2$ 行为计策的策略表。
输出格式
如果 $\mathrm{type} = 1$，输出一行一个浮点数表示决策的胜率，和标准答案的绝对误差在 $10^{-6}$ 之内均算作正确。
如果 $\mathrm{type} = 2$，输出一个策略表，设该策略表对决策的策略表的胜率为 $x$，我们提供的参考解胜率为 $y$，那么当 $x>y-10^{-6}$ 时算作正确。
如果 $\mathrm{type} = 3$，输出一个策略表，我们会生成一张策略表，设你的策略表对我们的策略表的胜率为 $x$，那么当 $x>0.5-10^{-6}$ 时算作正确。
注：测评时为了防止精度误差，在假如某个状态只有低于 $10^{-8}$ 的概率转移出死循环时直接将该状态胜率置为 $0.5$。
样例一
input
0 1 1 2 3 -1 0 1 0 0 1 0 0 0 -1 0 0 0 0 1000000000 0 1000000000 0 0 0 1000000000 333333334 333333333 333333333 0 0 1000000000 0 1000000000 0 0 0 1000000000 333333334 333333333 333333333
output
0.5000000000
样例二
input
0 1 2 2 3 -1 0 1 0 0 1 0 0 0 -1 0 0 0 0 1000000000 0 1000000000 0 0 0 1000000000 333333334 333333333 333333333
output
0 0 1000000000 0 1000000000 0 0 0 1000000000 333333334 333333333 333333333
样例三
input
0 1 3 2 3 -1 0 1 0 0 1 0 0 0 -1 0 0
output
0 0 1000000000 0 1000000000 0 0 0 1000000000 333333334 333333333 333333333
限制与约定
| 测试点编号 | $\mathrm{Case}$ | $n$ | $m$ | $\mathrm{type}$ | 备注 |
|---|---|---|---|---|---|
| 1 | $= 1$ | $= 5$ | $= 30$ | $1$ | 输入见样例数据及1号点下载中的 jc1.in |
| 2 | $= 100$ | 无 | |||
| 3 | $= 100$ | $= 3$ | $= 5$ | $2$ | 无 |
| 4 | $= 30$ | $= 5$ | $= 30$ | ||
| 5 | $= 1$ | $= 3$ | $= 3$ | $3$ | 游戏局面与样例一相同 |
| 6 | $= 1$ | $= 5$ | $= 3$ | ||
| 7 | $= 100$ | $= 2$ | $= 5$ | 无 | |
| 8 | $= 100$ | $= 5$ | $= 5$ | ||
| 9 | $= 100$ | $= 2$ | $= 30$ | ||
| 10 | $= 10$ | $= 5$ | $= 30$ |
除了第 5,6 两个点，其他点数据均为随机生成。
随机生成方式：
- 对于每个技能，有 $\frac{1}{3}$ 的概率是免费型，$\frac{1}{3}$ 是消耗型，$\frac{1}{3}$ 是补给型，且消耗型和补给型的 $x$ 的绝对值不超过 $3$。
- 保证三种技能至少都有一个。
- 小技能的相克关系生成方式：
- 对于每一对技能，有 $20\%$ 的概率有相克关系：
- 假如使用后能量损失相同则各有 $50\%$ 概率克对方。
- 假如使用后不同则收益大的一方有 $20\%$ 的概率克对方，收益小的一方有 $80\%$ 的概率克对方。
- 保证每个补给型技能至少被一个技能克。
- 保证至少存在一个补给型技能使得只有消耗型技能才能克它。
- 对于每一对技能，有 $20\%$ 的概率有相克关系：
- 策略表生成方式：
- 对于一个状态，把可使用的小技能的使用概率置为均等。由于必须要是 $10^{-9}$ 的整数倍有可能无法均匀分配，保证任意两个可使用的小技能的使用概率之差的绝对值不超过 $10^{-9}$。
- 然后进行 $100$ 次操作，每次操作选择两个不同的可使用的小技能 $i, j$，产生一个 $10^{-9}$ 到 $i$ 技能的使用概率之间的均匀随机数 $\delta$，且 $\delta$ 为 $10^{-9}$ 的整数倍。将 $i$ 的概率减少 $\delta$，将 $j$ 的概率加上 $\delta$。
如果不理解可以参考1号点。
时间限制：$2\texttt{s}$
空间限制：$256\texttt{MB}$
来源
中国国家集训队互测2015 - By 邹逍遥