진화

Beverly 박사는 특이한 생물을 연구하고 있다. 이 생물의 DNA는 크기가 $d$인 알파벳에서 고른 $k$개의 문자로 이루어진 하나의 문자열이다. 개체는 태어난 지 한 시간 뒤에 정확히 하나의 자손을 낳고, 그 뒤로도 잠시 더 살아간다. 이 과정이 세대마다 반복되어 하나의 직계 혈통을 이룬다.

자손이 태어날 때 그 DNA는 부모의 DNA를 복제한 것이지만, $k$개의 문자는 각각 독립적으로 돌연변이를 일으킬 수 있다. 각 문자는 확률 $p$로 돌연변이하여 크기가 $d$인 알파벳에서 균등한 확률로 고른 문자로 바뀐다(우연히 같은 문자가 될 수도 있다). 확률 $1 - p$로는 문자가 그대로 유지된다. 따라서 부모에서 자식으로 한 세대가 지날 때, 어떤 한 문자가 특정한 목표 문자와 같게 유지될 확률은 $(1 - p) + p/d$이고, 특정한 다른 문자로 바뀔 확률은 $p/d$이다. 문자열 전체의 전이 확률은 $k$개 위치에 대한 곱이다.

Beverly 박사는 개체 하나로 실험을 시작했지만, 곧 딴 데 정신이 팔려 실험을 잊어버렸다. 한참 뒤 돌아와 보니 $N$마리의 사체가 남아 있었는데, 이는 최초 개체와 그 자손들이 이어진 혈통 전체였다. 하지만 박사는 이들의 출생 순서를 더 이상 알지 못한다. 박사는 $N$개의 DNA를 모두 채취했다. 채취한 각 개체에 대해, 그 개체가 실험을 시작한 최초 개체였을 확률을 구하여라.

사전적으로 $N$마리 각각이 최초 개체였을 확률은 모두 같다고 가정하며, $N$개의 문자열은 무작위 순서로 주어진다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 세 정수 $N$, $k$, $d$와 실수 $p$가 공백 하나로 구분되어 주어진다. 이때 $1 \le N \le 15$, $1 \le k \le 8$, $1 \le d \le 4$, $0.2 \le p \le 0.5$이다.
• 이어지는 $N$개의 줄에는 각각 크기가 $d$인 고정된 알파벳(모든 문자열에 대해 동일하며 대문자 A–Z의 부분집합) 위에서 정의된 길이 $k$의 문자열이 주어진다. $i$번째 줄의 문자열은 $i$번째 개체의 DNA이다.

각 테스트 케이스마다 $N$개의 줄을 출력한다. $i$번째 줄에는 입력에서 $i$번째로 주어진 개체가 최초 개체였을 확률을 소수점 아래 여섯 자리까지 반올림하여 출력한다.