题目描述

人们正在踢足球，分成两个队。每个球员都穿着队服，上面印着一个在队中独一无二的 $1$ 到 $N$ 间正整数，包括 $1$ 和 $N$。

对于每个玩家，我们知道他的精准度，知道他能把球传给的队友（集合 $F$ ），也知道能抢断他的对手（集合 $E$ ）。

当一名球员恰好接得一球之后的一秒后有以下情况中的一种会发生:

• 球员将球传给随机一名队友

• 随机一位对手将球夺过

• 球员试图向球门射门

如果球员试图射门，得分的概率等于他的精准度。无论射门成功与否，将球判给对方的 $1$ 号球员。

不同事件的可能性为比例 $|F|:|E|:1$，仅依赖于当前持球的玩家（ $|S|$ 代表集合 $S$ 的大小）。

“随机”一词指的是集合 $F$（或 $E$ ）中的所有玩家均有相同的概率从目前持球的球员那里拿到传的球。

不需计算传球的时间。

比赛以队伍一的球员 $1$ 控球开始，当一个球队进了 $R$ 个球，或者 $T$ 秒过去了，比赛结束（以两者中先发生的时间为准）。对于每一个可能的进球，计算出比赛以它结束的概率。

输入格式

第一行包含三个正整数 $N,R,T$，分别表示每个队伍中球员的人数，赢得比赛需要的进球数和比赛的时长。

接下来的 $N$ 行，描述队伍一的球员的信息；再下来的 $N$ 行，描述队伍二的球员的信息。

对于每一个球员的信息，一个实数 $p$，表示此球员的精准度；两个正整数 $N_f,N_e$，分别表示此球员的队友数和敌人数；接下来 $N_f$ 个数，为此球员的队友的编号；接下来 $N_e$ 个数，为此球员的敌人的编号。

注意：此球员的队友编号中不会包含此球员的编号。

输出格式

共 $R\times (N+2)$ 行，每行一个实数，表示比赛以此进球结束的概率。

先按照时间顺序输出队伍一的进球，再按照时间顺序输出第二队的。

输出的答案与标准答案相差 $\le 0.000001$ 即视为正确。

1 1 2
0.5 0 1 1
0.5 0 1 1

0.56250
0.18750
0.25000

2 2 5
0.0 1 2 2 1 2
1.0 0 0
0.5 1 0 2
0.5 1 0 1

0.2578125
0.2812500
0.0703125
0.1718750
0.1640625
0.0234375
0.0156250
0.0156250

提示

【样例解释#1】

比赛只持续 $2$ 次移动或直到某人得分。由于 $N=1$，比赛中只有两名选手，两个选手的射门精确度都是 $0.5$，也就是说每个人的精确度都是 $50\%$。

让我们将灰色玩家标记为 $A$，将白色玩家标记为 $B$。在这些假设下，只有 $6$ 个可能的情况。下表分别描述了这些情况和对应的概率：

通过把这些概率加在一起，我们可以得到答案：

【数据范围】

对于 $100\%$ 的数据，$1\le N\le 100$，$1\le R\le 10$，$1\le T\le 500$，$0\le p\le 1$，$0\le N_f\le N-1$，$0\le N_e\le N$。

【说明】

本题 spj 用于判断答案精确度。

本题分值按 COCI 原题设置，满分 $160$。

题目译自 COCI2012_2013 CONTEST #5 T6 MNOGOMET。