Evolution

Dr. Beverly studies an unusual organism whose DNA is a single string of $k$ letters drawn from an alphabet of size $d$. One hour after it is born, an individual produces exactly one offspring, and then lives on for a short while longer. This repeats generation after generation, forming a single line of descent.

When an offspring is produced, its DNA is copied from its parent, but each of the $k$ letters may mutate independently. With probability $p$ a given letter mutates: it is replaced by a letter chosen uniformly at random from the size-$d$ alphabet (which may, by chance, be the same letter). With probability $1 - p$ the letter is left unchanged. Consequently, for one parent-to-child step, a fixed letter stays equal to a given target letter with probability $(1 - p) + p/d$, and becomes a specific different letter with probability $p/d$; the transition probability of a whole string is the product over its $k$ positions.

Dr. Beverly began an experiment with a single individual, then got distracted and forgot about it. Returning later, she found the remains of $N$ creatures — the original individual together with its unbroken chain of descendants — but she no longer knows their birth order. She sampled all $N$ DNA strings. For each sampled creature, compute the probability that it was the original individual with which the experiment began.

Assume that, a priori, each of the $N$ creatures is equally likely to have been the original, and that the $N$ strings are presented in a random order.

The first line contains a single integer $T$, the number of test cases. Each test case has the following format:

• One line with three integers $N$, $k$, $d$ and one real number $p$, separated by single spaces, where $1 \le N \le 15$, $1 \le k \le 8$, $1 \le d \le 4$, and $0.2 \le p \le 0.5$.
• $N$ following lines, each containing a string of length $k$ over a fixed alphabet of size $d$ (a subset of the uppercase letters A–Z, the same alphabet for all $N$ strings). The string on the $i$-th line is the DNA of the $i$-th creature.

For each test case, output $N$ lines. The $i$-th line contains the probability that the $i$-th creature given in the input was the original individual, rounded to exactly six digits after the decimal point.