Kim goes to see a doctor regularly. But Kim’s English is very poor. So, when the doctor asks Kim about how he feels about himself, there are only m answers that Kim will say, such as “I feel good”, “I feel cold”, “I feel dizzy”, etc.
There are n diseases that Kim will suffer from, such as “Healthy”, “Fever”, “Stomache”(You should be careful that in this problem, healthy is also a kind of “disease”).
After a very long period, the doctor discovered that when Kim is suffering from a specific disease, the probability of each response Kim will give to the doctor is fixed.
For example, consider that there are 3 diseases in total, “Healthy”, “Fever” and “Stomache”, and 3 answers in total, “I feel good”, “I feel cold” and “I feel dizzy”. When Kim have a fever, the probability that he will say “I feel good” is 0.3, the probability that he will say “I feel cold” is 0.65 and the probability that he will say “I feel dizzy” is 0.05.
We can rewrite it in mathematics formulas, that is P(I feel good|fever) = 0.3, P(I feel cold|Fever) = 0.65, and P(I feel dizzy|Fever)=0.05.
Besides, the doctor also discovered that when Kim has suffered from a specific disease, next time when he goes to see the doctor, the probability that he is suffering from a specific disease is also fixed.
For example, there’re also 3 diseases in total. On the previous meeting, Kim had a “fever”. Now, on this meeting, the probability that he is “healthy” is 0.3, the probability that he had a “fever” is 0.5, and the probability that he has a “stomache” is 0.2.
We can also rewrite it in mathematics formulas, that is P(Healthy|Fever) = 0.3, P(Fever|Fever) = 0.5, and P(Stomache|Fever)=0.2.
Now, we’ve already known that Kim had seen this doctor k times, and we’ve already known how Kim had responded each time.
To make this problem simpler, we assume that the on the first meeting, the probability of each diseases that Kim may be suffering from is fixed.
Please give me a sequence D of diseases that Di is the disease that Kim was suffering from on the i_th meeting, which satisfied that the probability of this sequence of diseases actually be suffered by Kim is maximum.
First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.
In each test case:
There’re 3 integers in the first line: n, m, k.
There are n real numbers in next n lines. The j_th number in the i_th line indicates that when Kim suffered from thet i_th disease last time, the probability that he is suffering from the j_th disease this time.
There are m real numbers in next n lines. The j_th number in the i_th line indicates that when Kim suffered from the i_th disease, the probability that he’ll say the j_th answer.
n real numbers in the next line, the i_th number indicates that in the first time, the probability that Kim was suffering from the i_th disease.
K integers in the next line which are the response that Kim gave to the doctor each time.
1 <= N,M,K <= 300
K integers in a line, which is the sequence of disease with maximum probability.
1 2 3 3 0.7 0.3 0.4 0.6 0.5 0.4 0.1 0.1 0.3 0.6 0.6 0.4 1 2 3
1 1 2