Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
74 - ZOJ Monthly, January 2009 - B
Dareda?

Time Limit: 1 Second      Memory Limit: 16384 KB

Vegetable Bird: The problem "Dareda?" has been rejudged three times.
T_T: .... a deep hole, and I jumped in again =,=b
hhanger: pia the author.
Fire: pia watashi.
watashi: T_T.
Linyue: How do you know the author is watashi.
xgy: re, the author is not watashi, but rejudge.

People have many features, some features help to distinguish a person from the others. So given a discription of a person, sometimes you can guess who he or she is, but sometimes you're wrong. Knowing the probability distribution of different groups of people and the probability distribution of people who are in the same group but are different in some aspects, can you answer what the probability that a person belongs to certain group is? It's guaranteed that the groups are disjoint and any person belongs to at least and at most one group. You can assume that different aspects are independent.

Input

There are multiple cases. Each case begins with two integers n and m, then m(0 <= m <= 16) different words("[A-Za-z0-9_]{1,256}") specifying the aspects you need to consider about.

There are n(0 <= n <= 16) different groups of people. Each group begin with "GROUP_NAME PROBABILITY%" where PROBABILITY is the probability that a random person belongs to group GROUP_NAME. Then m lines each describes the probability distribution in aspect ASPECT_NAME in format "ASPECT_NAME cnt (FEATURE_TYPE P%){cnt}"(more details in sample), where cnt is a nonnegative integer no more than 16 and P is the probability that a random person from group GROUP_NAME has feature FEATURE_TYPE.

There are q(0 <= q <= 100) queries following the number q. Their format is "query.gao\?ASPECT_NAME=FEATURE_TYPE(&ASPECT_NAME=FEATURE_TYPE)+". If the feature in some aspect is not specified, then any FEATURE_TYPE will be OK, or the people must have feature FEATURE_TYPE in aspect ASPECT_NAME. You can assume that ASPECT_NAME is always one of the given m aspects. The same aspect may occur more than once in a query.

Output

For each case, first output <answer cid=#> where id is the case number, then q lines replies in format <reply( GROUP_NAME=PROBABILITY%)+ />(more details in sample), where GROUP_NAME is the group in input order and PROBABILITY (with three decimal digits) is the probability that the discribed people belongs to group GROUP_NAME. At the end of each case, output </answer>.

Sample Input

2 3
i_am_a rp_value rejudge_times
watashi 50%
i_am_a 1   ppmm 100%
rp_value 2   0 50%   -1 50%
rejudge_times 4   0 40%   1 30%   2 20%   3 10%
rejudge 50%
i_am_a 1   ppmm 100%
rp_value 2   0 50%   1 50%
rejudge_times 4   3 10%   4 20%   5 30%   6 40%
2
query.gao?i_am_a=ppmm&rp_value=0&rejudge_times=3
query.gao?i_am_a=ppmm&rp_value=3&rejudge_times=0
2 1
gender
human 50.0%
gender 2	male 50.0%	female 50.0%
martian 50.0%
gender 4	male 30.0%	female 30.0%	both 20.0%	neither 20.0%
4
query.gao?gender=male
query.gao?gender=male&gender=female
query.gao?gender=both
query.gao?gender=either

Sample Output

<answer cid=1>
<reply watashi=50.000% rejudge=50.000% />
<reply watashi=0.000% rejudge=0.000% />
</answer>
<answer cid=2>
<reply human=62.500% martian=37.500% />
<reply human=0.000% martian=0.000% />
<reply human=0.000% martian=100.000% />
<reply human=0.000% martian=0.000% />
</answer>

Note

TAB is used instead of space in some place to make the input more clear.


Author: WU, Zejun
Source: ZOJ Monthly, January 2009
Submit    Status