题目描述

$2N$ people are playing football (soccer), divided into two teams. Each player wears a dress with the team logo and a unique (in the team) positive integer between $1$ and $N$, inclusive. For each player, we know his precision, the set of teammates whom he can pass the ball to ($F$) and the set of opponents who can take the ball from him ($E$). When a player comes into possession of the ball, after exactly one second one of the following events will happen:

• the player passes the ball to a random teammate from the set $F$;
• a random opponent from the set $E$ takes the ball from him;
• the player attempts a shot at the goal.

If the player attempts a shot, the probability of scoring a goal is equal to his precision. After the shot, whether it was successful or not, the ball is awarded to the player number $1$ from the opposing team.

The probabilities of different events are in the proportion $|F| : |E| : 1$, in order, and depend only on the player currently in possession of the ball ( $|S|$ determines the size of the set $S$ corresponding to the current player), not on any previous events in the game. The word "random" means that all players from the set $F$ (or $E$) have the same probability of being passed (or taking) the ball by (from) the player that is currently in the ball's possession. The time that a ball spends outside of a player's possession is negligible.

The match begins with player $1$ from the first team in possession of the ball and ends either when one team has scored $R$ goals or when $T$ seconds have elapsed, whichever happens first. For each possible final score, determine the probability that the match will end with it.

输入格式

The first line of input contains three positive integers: $N$ ( $1 \le N \le 100$ ), the number of players in each team, $R$ ( $1 \le R \le 10$ ), the number of goals needed for victory, and $T$ ( $1 \le T \le 500$ ), the maximum duration of the match.

The following $N$ lines contain descriptions of the first team's players, one per line, while the next $N$ lines after that contain descriptions of the second team's players. A description of a single player consists of a real number $p$ ( $0 \le p \le 1$ ), the player's precision, followed by two positive integers, $nF$ ( $0 \le nF \le N - 1$ ) and $nE$ ( $0 \le nE \le N$ ), the sizes of the sets $F$ and $E$, respectively, followed by $nF + nE$ player labels representing the sets $F$ and $E$ themselves (in that order), all space-separated. Note that the labels from $F$ represent players from one team, and labels from $E$ the other team. The set $F$ will not contain the label of the player currently being described.

输出格式

The match can theoretically end with one of $R \times (R + 2)$ different final results. For each result, output the probability of its realization as a real number, one per line. Order the results first by the number of goals scored by the first team, then by the number of goals scored by the second team, in ascending order. The permitted difference from the exact value for each probability is $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

提示

Clarification of the first example: The star denotes the player in possession of the ball in the beginning. The match lasts for only $T = 2$ moves or until someone scores $R = 1$ goal. Since $N = 1$, there are only two players in the match, playing one against the other. Both players have the precision of $0.5$, which means that each has a $50\%$ chance of scoring a goal when trying to shoot, after which the ball is awarded to the opponent.

Let us label the grey player as A, and the white player as B. Under these assumptions, there are only $6$ possible matches. Each of them is described in the table below, with the corresponding probability, description and outcome:

Probability	Description	Outcome
$0.25$	A decides to shoot and scores!	1:0
$0.25 \times 0.25$	A decides to shoot, but misses. 0:1 B decides to shoot and scores!	0:1
	A decides to shoot, but misses. 0:0 B decides to shoot, but also misses.	0:0
$0.50 \times 0.25$	A loses the ball to B. 0:1 B decides to shoot and scores!	0:1
$0.50 \times 0.50$	A loses the ball to B. 0:0 B loses the ball to A.	0:0
$0.50 \times 0.25$	A loses the ball to B. 0:0 B decides to shoot, but misses.

By summing probabilities for particular final results, we obtain the following solution:

Result	Probability
0:0	$0.25 \times 0.25 + 0.5 \times 0.5 + 0.5 \times 0.25 = 0.5625$
0:1	$0.25 \times 0.25 + 0.5 \times 0.25 = 0.1875$
1:0	$0.25$

Source:COCI2012_2013 CONTEST #5 T6 MNOGOMET