Monkeys at Typewriters

Time limit1sMemory limit128 MB

Summary

Given per-letter and space probabilities, find the probability that a random key sequence terminates at its first space in one of the given words.

Level: Medium6 of 10
Topics: Probability, Trie, Dynamic programming, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

2
2 2 0.5
a 0.5
b 0.0
abba
baa
2 2 0.4
a 0.5
b 0.1
abba
babbbb

Expected output

Data Set 1:
0.0000E+00

Data Set 2:
1.0020E-03

Example 2

Input

1
1 1 0.5
a 0.5
a

Expected output

Data Set 1:
2.5000E-01

Example 3

Input

1
2 2 0.5
a 0.3
b 0.2
a
b

Expected output

Data Set 1:
2.5000E-01