说明

$2N$ 个球员正在踢足球，分成两个队伍。每个球员都穿着队服，上面印着一个在队中独一无二的 $1$ 至 $N$ 的正整数编号，包括 $1$ 和 $N$。对于每个球员，我们都知道他的精准度、他能把球传给的队友集合 $F$、以及能抢断他的对手集合 $E$。当一名球员接到球的恰好一秒后，会发生以下情况中的一种:

• 球员将球传给集合 $F$ 中的随机一名队友；
• 集合 $E$ 中的随机一位对手将球夺过；
• 球员试图射门。

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

这些事件发生概率的比例依次为 $|F|:|E|:1$，即只由目前持球的玩家决定，与之前发生的事件无关，其中 $|S|$ 代表集合 $S$ 的大小。“随机”一词指的是集合 $F$ 或 $E$ 中的所有球员均有相同的概率被选中。不需要考虑传球的时间。

比赛以第一个队伍的球员 $1$ 持球开始，并在某一个球队进了 $R$ 个球或者 $T$ 秒后结束（以两者中先发生的时间为准）。对于每一种可能的最终比分，输出比赛以该比分结束的概率。

输入格式

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

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

每一个球员的信息占一行，包含：一个实数 $p$，表示此球员的精准度；两个正整数 $N_F,N_E$，分别表示集合 $F$ 和 $E$ 的大小；接下来 $N_F$ 个数，表示集合 $F$ 中的元素；接下来 $N_E$ 个数，表示集合 $E$ 中的元素。

注意：集合 $F$ 中不会包含这个球员自身。

输出格式

比赛有 $R\times(R+2)$ 种不同的最终比分。将所有可能的比分以第一个队伍进球数作为第一关键字，第二个队伍进球数作为第二个关键字进行升序排序后，按照该顺序对于每一种可能的比分输出一行一个实数表示比赛以该比分结束的概率。

输出的答案与标准答案相差不超过 $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。