Football Game Markov Chain

In this problem, two football teams (Team 1 and Team 2) each have N players. In each team the players wear jerseys numbered uniquely from 1 to N. The match starts with Team 1’s player 1 holding the ball.

For every player, three pieces of information are given:

• The player’s accuracy, a real number between 0 and 1.
• A set F of teammates (identified by their jersey numbers) to whom he can pass the ball.
• A set E of opponents (identified by their jersey numbers in the opponent team) who can steal the ball from him.

One second after a player exactly receives the ball (or at the very start, after time 0), one of the following events occurs:

• The player passes the ball to a random teammate (each teammate in F is chosen equally).
• A random opponent from E steals the ball (each opponent in E is chosen equally).
• The player attempts to shoot at the goal. The probability that the shot results in a goal is equal to his accuracy. Regardless of whether the shot is successful or not, after the shooting the ball is awarded to the opponent team’s player 1.

The three kinds of events occur with relative probabilities proportional to |F| : |E| : 1 respectively (where |S| is the size of set S). That is, if a player’s F and E have sizes f and e, then the probabilities are:

[ P(\text{pass})=\frac{f}{f+e+1},\quad P(\text{steal})=\frac{e}{f+e+1},\quad P(\text{shoot})=\frac{1}{f+e+1}. ]

The game lasts until one team has scored R goals, or until T seconds have passed – whichever occurs first. Note that each event takes exactly 1 second, and an event is processed only if the current time is less than T (i.e. when time reaches T the game immediately stops and any state with no event is considered a timeout).

Your task is to compute the probability that the game ends with a goal by each team. In other words, if a shot results in a goal and that goal makes the shooting team reach R goals (thus ending the match), add the probability of that event to that team’s winning probability. Note that if the game ends because of a timeout, it does not count.

Input/Output Format: See below.

inputFormat

The input is given as follows:

N R T
// Next N lines for Team 1 players (players numbered 1 to N)
accuracy fCount f1 f2 ... f_(fCount) eCount e1 e2 ... e_(eCount)
// Next N lines for Team 2 players (players numbered 1 to N)
accuracy fCount f1 f2 ... f_(fCount) eCount e1 e2 ... e_(eCount)

Each accuracy is a floating‐point number between 0 and 1. For each player, first the accuracy is given, then the number of teammates available for passing and the list of their jersey numbers, followed by the number of opponents who can steal and the list of their jersey numbers. It is guaranteed that the jersey numbers in each team are from 1 to N and unique.

outputFormat

Output two floating‑point numbers with at least 6 digits after the decimal point, representing the probability that the game ends with a goal scored by Team 1 and Team 2 respectively.

sample

1 1 1
1.0 0 0
1.0 0 0

1.000000 0.000000