문제

Author: Anton Grbin

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: o the player passes the ball to a random teammate from the set F, o a random opponent from the set E takes the ball from him, o 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 following image illustrates the player arrangement for the second test example:

입력

The first line of input contains three positive integers: N (1 ≤ N ≤ 100), the number of players in each team, R (1 ≤ R ≤ 10), the number of goals needed for victory, and T (1 ≤ T ≤ 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 ≤ p ≤ 1), the player's precision, followed by two positive integers, nF (0 ≤ nF ≤ N - 1) and nE (0 ≤ nE ≤ 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. Author: Anton Grbin

출력

The match can theoretically end with one of R * (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 goas scored by the second team, in ascending order. The permitted difference from the exact value for each probability is 0.000001.

예제 입력 1

1 1 2
0.5 0 1 1
0.5 0 1 1

예제 출력 1

0.5625000000
0.1875000000
0.2500000000

예제 입력 2

2 2 5
0 1 2 2 1 2
1 0 0
0.5 1 0 2
0.5 1 0 1

예제 출력 2

0.2578125000
0.2812500000
0.0703125000
0.1718750000
0.1640625000
0.0234375000
0.0156250000
0.0156250000