2351: Evolution

    Dr. Beverly has been experimenting with an interesting kind of organism. This organism’s DNA
consists of a single string of k letters over some alphabet of size d. One hour after its birth, an
individual gives birth to one offspring, after which it happily lives on for another 15 minutes or
so. This process repeats until there is no cold pizza left to feed on.
    A mutation is a replacement of a character in the string with any character from the alphabet,
possibly with itself. Mutations may occur from one generation to the next. The probability of a
mutation is the same for each of the characters of the alphabet and is denoted by p.
    Unfortunately, after Dr. Beverly started an experiment with one such creature, she got so
caught up in a computer game of some kind that she forgot all about her experiment. When she
came back a while later, she found the remains of N creatures. She sampled their DNA, hoping she
would be able to figure out which of the corpses belongs to the creature she started the experiment
with. Oh if only she had made notes! Anyway, given N strings of DNA, can you compute the
probability for each individual that it was the original creature? We may assume that each of the
N strings is (a priori) equally likely to serve as the initial string. The order in which the N strings
are given is random.

The first line of the input contains a single number: the number of test cases to follow. Each test
case has the following format:
• One line with three integers N, k and d, satisfying 1 ≤ N ≤ 15, 1 ≤ k ≤ 8, 1 ≤ d ≤ 4 and a
real number p, satisfying 0.2 ≤ p ≤ 0.5. The numbers are separated by single spaces.
• N lines, each with a string of length k over some alphabet of size d. This alphabet is a
subset of { A, B, C, . . . , Z } and is the same for all N strings. The string on the i-th line
represents the DNA of the i-th creature.

For every test case in the input, the output should contain N lines, each with a real number,
rounded and displayed to six digits after the decimal point. The number on the i-th line should
be the probability that the i-th creature in the input was the original creature.

2
3 1 2 0.25
A
C
C
4 4 4 0.50
GTTG
TGTG
TTTG
GTGT

0.466667
0.266667
0.266667
0.046602
0.393710
0.083333
0.476354