How many schemata survive

A genetic algorithm keeps a population of n strings of length l of zeros and ones; string i has fitness f_i. A new generation is produced as in the schema theorem: selection proportional to fitness, one-point crossover of pairs with probability p_c (the cut at one of l − 1 places), mutation of each bit with probability p_m.

A researcher wants to know which schemata the population will surely not lose. A schema is a string of length l of the symbols 0, 1 and *; a string matches the schema if it agrees with it at all positions where the schema has no asterisk. For each schema H compute the schema theorem’s lower bound for the mean number of matching strings in the next generation:

$$m(H)\cdot\frac{f(H)}{\bar f}\cdot\left(1 - p_c\,\frac{\delta(H)}{l - 1}\right)\cdot(1 - p_m)^{o(H)}.$$

Here m(H) is the number of matching strings, f(H) their mean fitness, f̄ the mean fitness of the whole population, o(H) the number of positions of the schema without an asterisk, δ(H) the distance between the first and last such positions (0 if there are fewer than two). If no strings match, the bound is 0. With l = 1 there is nowhere to cross, and the crossover factor is 1.

Input

The first line holds n, l, q (1 ≤ n ≤ 1000, 1 ≤ l ≤ 64, 1 ≤ q ≤ 1000). The second holds p_c and p_m (from 0 to 1). Then come n lines: a string of the population and its fitness, an integer from 1 to 10⁶. Then q schemata, one per line.

Output

For each schema, the bound, each on a new line. The answer is accepted if the error is at most 10⁻⁶ (relative for numbers greater than one).

4 4 4
0.7 0.01
1010 5
1110 3
0011 2
1000 2
1**0
*11*
****
0***

0.980100000
0.751410000
4.000000000
0.660000000

3 1 3
0.5 0.1
1 4
0 1
1 2
1
0
*

2.314285714
0.385714286
3.000000000