시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1 0 0 0.000%

문제

2N명이 두 팀으로 나누어서 축구를 하고 있다. 각 플레이어는 자기 팀의 유니폼을 입고 있고, 등번호는 1번부터 N번까지이다.

각 플레이어는 자신의 정확도를 알고 있고, 패스를 할 수 있는 팀 동료의 집합 F와 자신의 공을 빼았을 수 있는 상대팀 선수의 집합 E를 알고 있다.

플레이어가 공을 소유하게 되면, 그 순간부터 1초동안 아래 세 가지 중 하나의 사건이 발생한다.

  1. F에 속해있는 동료 중 한 명에게 패스를 한다. (랜덤)
  2. E에 속해있는 상대팀 선수 중 한 명에게 공을 빼앗긴다. (랜덤)
  3. 골대를 향해서 슛을 쏜다.

플레이어가 골대를 향해서 슛을 쏠 때, 득점할 확률은 자신의 정확도와 같다. 슛을 쏜 이후에는 결과에 상관없이 상대편 1번 선수가 공을 소유하게 된다.

위의 각 사건이 발생할 확률은 |F| : |E| : 1이고, 이전에 일어났던 사건은 여기에 영향을 미치지 않는다. (|S|는 집합 S의 크기이다) 각 사건의 설명 중에 랜덤은 각 집합에 포함되는 한 선수를 선택할 확률이 모두 같다는 것을 의미한다. 선수가 공을 소유하고 있지 않는 시간은 무시할 수 있을 만큼 매우 작다.

경기는 첫 번째 팀의 1번 선수가 공을 소유하면서 시작한다. 경기는 R 골을 득점한 팀이 있거나, 경기가 시작한지 T초가 지나면 끝나게 된다. 가능한 모든 최종 스코어에 대해서, 그 스코어로 경기가 끝날 확률을 계산하는 프로그램을 작성하시오.

아래 그림은 예제를 그림으로 나타낸 것이다.

입력

첫째 줄에 N, R, T가 주어진다. (1 ≤ N ≤ 100, 1 ≤ R ≤ 10, 1 ≤ T ≤ 500)

다음 N개 줄에는 첫 번째 팀에 속하는 각 선수의 설명이 주어지며, 그 다음 N개 줄에는 두 번째 팀에 속하는 각 선수의 설명이 주어진다.

선수의 설명에서 첫 번째 숫자는 그 선수의 정확도 p이다. (0 ≤ p ≤ 1) 그 다음에는 두 양의 정수 집합 F의 크기 nF와 집합 E의 크기 nE가 주어진다. (0 ≤ nF ≤ N-1, 0 ≤ nE ≤ N) 다음 nF+nE개 숫자는 각각 집합 F와 E에 포함되는 선수의 번호가 순서대로 주어지며, 공백으로 구분되어져 있다. 집합 F에는 자기 자신 번호를 포함하지 않는다.

출력

이론상 가능한 최종 스코어는 R*(R+2)개이다. 각 스코어에 대해서 그 결과가 나올 확률을 한 줄에 하나씩 출력한다.

출력하는 순서는 첫 번째 팀의 점수가 증가하는 순서로, 같은 경우에는 두 번째 팀의 점수가 증가하는 순서로 출력한다.

확률의 오차는 0.000001까지 허용한다.

예제 입력

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

힌트