The Game of Death

문제 정보

문제

남대나 다름없는 공대에 다니는 당신의 유일한 낙은 매 학기 초에 하는 단체 미팅이다. 적게는 수십명에서 수백명까지가 참여하는 이 단체 미팅의 백미는 바로 수백명이 한꺼번에 참여하는 The Game Of Death 이다.

The Game Of Death 의 룰을 모르는 사람을 위해: 원을 그리고 둘러 앉은 사람들이, 시작 신호와 동시에, 손을 들어올려 임의의 사람을 가리킨다. 이번 차례를 시작하는 사람이 어떤 숫자 n 을 외치면, 시작하는 사람으로부터 n번 손가락을 따라가서 끝에 있는 사람이 술을 한 잔 마시고 다음 차례를 시작하는 사람이 된다. 예를 들어, 태연이 소희를, 소희가 승연이를, 승연이가 유키를 가리키고 있는데, 태연이 3 을 외쳤다면 유키가 술을 한 잔 마셔야 한다.

당신이 게임을 시작할 차례가 되었다. "The Game of Death!" 를 외치고 당신은 다른 사람들이 각자 누구를 가리키고 있나 흘끔 쳐다본 후, 어떤 숫자 X 를 외쳤다.

당신은 이미 술을 좀 마셨기 때문에, 다른 사람들이 누구를 가리키고 있는지 정확하게 보지 못할 수도 있다. 예를 들어, 철수는 영희를 가리켰는데, 당신은 영희 옆에 있는 순이를 가리켰다고 생각할 수도 있는 것이다. 이 때, 당신의 관찰 결과는 항상 T명 이상 빗나가지 않는다고 하자. 예를 들어, 당신이 A가 B를 가리키고 있다고 관찰했다면, A가 실제로 가리키는 사람은 B 로부터 왼쪽으로 T명, 오른쪽으로 T명 안에 반드시 존재한다는 것이다. (T = 0 이면, 당신의 관찰 결과는 항상 정확하다) 편의를 위해, A가 이 사람들 중 각 사람을 가리킬 수 있는 확률은 모두 동일하다고 가정하자. 물론, 당신이 누구를 가리키고 있는지는 항상 정확히 알 수 있다고 한다.

당신은 미팅 상대방 중 몇 명을 맘에 두고 있다. 이 때, 이번 차례에 이 사람들이 술을 마시게 될 확률을 계산하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 수 C 가 주어진다. 각 테스트 케이스의 첫 줄에는 미팅에 참가한 사람의 수 N (5 <= N <= 200) 과 당신이 외친 숫자 X (0 <= X <= 1000000), 그리고 당신이 관심있어하는 상대방의 수 M (1 <= M <= 10), 그리고 당신 관찰의 오차인 T (0 <= T < N/2) 가 주어진다. 다음 줄에 당신의 관찰 결과 Ai (1 <= Ai <= N) 가 N개의 정수로 주어진다. 이들은 1번 사람부터 N번 사람까지 각각 가리킨 사람의 번호이다. 그 다음 줄에 M개의 정수로, 당신이 관심있어하는 상대방의 번호 Bi (1 <= Bi <= N) 가 주어진다.

1번부터 N번까지 순서대로 원을 그리고 앉아 있다고 가정하며, 당신의 번호는 1번이다.

출력

각 테스트 케이스마다 한 줄의 결과를 출력한다. 각 줄에는 주어진 M명의 관심 있는 사람에 대해, 각각 이번 차례에 술을 마실 확률을 출력한다. 확률은 소수점 아래 다섯 번째 자리까지 반올림하여 출력한다.

예제 입력

2
2 3 1 0
2 1
2
10 1000000 10 4
2 3 4 5 6 7 8 9 10 1
1 2 3 4 5 6 7 8 9 10

예제 출력

1.00000
0.09091 0.18182 0.08979 0.09203 0.09090
0.09092 0.10101 0.08081 0.09103 0.09078

노트

11개의 댓글이 있습니다.