Girl Friend II

After a long time of effort, RoBa still keeps single. He finds that all the girls are so hard to understand. They can become happy in one minute, and then get angry in the next. What’s more, what they do is usually quite different from what they think!

As an algorithmic geek, RoBa builds a probability model to study a girl’s behavior. That is, there are N kinds of inner states for one girl. At the beginning, the girl can be at state i with probability Si. Then at every minute after that, the girl’s state can be changed from state i to state j with probability Pij. Of course, S1+S2+…+SN = 100 (in percent), and for all the i, Pi1+Pi2+…+PiN=100

And that’s still not practical enough. RoBa knows that he cannot see the inner state of a girl directly, but can only see her outer behavior. There are M kinds of behaviors, and when a girl is at state i, she will take behavior k with probability Aik. And again, for all the i, Ai1+Ai2+…+AiM=100

Now, given a sequence of a girl’s outer behavior and all the probabilities describe above (we don’t know how RoBa get them!), can you help him to find out the girl’s most probable inner state sequence?

For example, as the figure above described, RoBa observes a girl for three minutes, and the behavior sequence is laugh -> Silent -> Silent. Then the poor boy wants to guess the girl’s real state. Let’s suppose he make a guess that the girl’s inner state sequence is happy -> sad -> happy. With the probabilities above, he can find its possibility is SHappy * AHappy,Laugh * PHappy,Sad * ASad,Silent * PSad,Happy * AHappy,Silent. So RoBa can calculate the possibility of all the inner state sequence, for example, sad->sad->happy, happy->happy->happy, and so on. Then he just simply picks the sequence with the highest possibility as the answer. Of course, this will cost too much time, so RoBa need a more clever algorithm to achieve the same result.

To be more formally, given a girl’s outer behavior sequence (B1, B2, … BT), it is natural that the possibility of a girl’s inner sequence (C1, C2, … CT) is

Don’t be scared of the formula above, it just describe our intuition precisely. This problem is not such difficult as it seems, believe me .

There are several test cases in the input.

The first line of each test case contains N and M, (1 <= N, M <= 50), the second line contains N numbers S1, S2, …, SN, that is, the probability of girl’s initial states. Then an N*N matrix follow, whose entry in the i-th row and j-th column is Pij, that is, the probability of the girl’s transition from state i to state j. Then an N*M matrix follow, whose entry in the i-th row and k-th column is Aik, that is, the probability of the girl’s behavior is k when she is at state i. As the definition, the sum of each row of the two matrices is 100, and every entry in the matrices is an integer in the range [0,100]. And the last line begins with an integer T (1 <= T <= 50), indicating the observe time of RoBa, then T integers follow, indicating the girls outer behavior sequence. All the T integers are in the range [1..M].

You can assume the observation sequence is always possible in the input, that is, with probability greater than 0.

Output T integers in one line for each case, indicating this girl’s most probable inner state sequence. All the integers should be in the range [1..N], of course. You will get accepted if the possibility of your output is close enough to the standard output.

2 2
50 50
50 50
50 50
50 50
50 50
2 1 2

2 2
0 100
50 50
49 51
50 50
50 50
2 1 2

1 1
2 2

Hint: The first case indicating a rather “random” girl, all the initial states, transition, and behavior are of equal possibility,
so the four possible inner state sequences 1-1, 1-2, 2-1, 2-2 are of equal possibility. In the second case, the girl is at state 2 definitely at the beginning.
Then there is a little bigger chance to change to state 2 than state 1, so the sequence 2-2 is more possible than 2-1.

2009 Multi-University Training Contest 2 - Host by TJU