Monkeys at Typewriters

You have probably heard that if you sat enough monkeys at typewriters and let them type for long enough, they would eventually reproduce all of Shakespeare's works — the idea being that each monkey hits a completely random sequence of keys.

Here we solve a related question. A monkey presses keys at random and stops the moment it hits the space bar for the first time. Each press is independent: the monkey hits a particular lowercase letter with a given probability, or the space bar with probability $s$, and all of these probabilities sum to $1$. The letters typed before that first space form the word the monkey produced; the monkey is said to have typed a given word exactly when this sequence equals the word.

Given a list of distinct lowercase words, compute the probability that the monkey ends up typing one of them.

The first line contains the number of data sets $K$. Each data set has the following form.

The first line contains three values $n$, $m$, and $s$ ($1 \le n \le 100$, $1 \le m \le 26$, $0 \le s \le 1$): $n$ is the number of target words, $m$ is the number of letter keys on the typewriter, and $s$ is the probability of hitting the space bar.

The next $m$ lines each contain a lowercase letter and a floating-point number: the probability of hitting that letter. Together with $s$, these probabilities add up to $1$.

The following $n$ lines each contain one word $w_i$. Each word consists only of lowercase letters that appear on the typewriter and has between $1$ and $20$ characters. All words in a data set are distinct.

For each data set, print Data Set x: on its own line, where $x$ is the index of the data set (starting from $1$). On the next line, print the probability that the monkey types at least one of the given words.

Because these probabilities can be extremely small, print each one in scientific notation with exactly four digits after the decimal point in the mantissa and a signed, at-least-two-digit exponent — for example, 3.7602E-13 or 0.0000E+00.

Print a blank line between consecutive data sets.