Weather
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 166 Accepted Submission(s): 15
Problem Description
Hovey Chen is going to Azeroth! "I have reached Darnassus." Hovey told Eliane Su, his girlfriend. Each day, Hovey called Eliane, and told her his feeling at Azeroth. "It's a good day today. We are going to hunt some Goblin :)" "It's raining and raining. We can do nothing but sleeping :("
Several days later, Hovey was missing Eliane so much. So he came back to the Earth. He wants to write a travel note for his friends. However, he forgets where he had been! What's worse, he never told Eliane he route. Luckily, he told Eliane the weather in his everyday report, and Eliane wrote it down on her notebook. Hovey knows the probability he went from one place to another. Given the probability from Darnassus to Booty Bay be p, it means that if Hovey is at Darnassus today, the chance he is going to Booty Bay tomorrow is p. Eliane knows the probability of given place to be in given weather. Now given the first place, and the two probability matrices, can you help Hovey to figure out the route which has the greatest probablity.
Several days later, Hovey was missing Eliane so much. So he came back to the Earth. He wants to write a travel note for his friends. However, he forgets where he had been! What's worse, he never told Eliane he route. Luckily, he told Eliane the weather in his everyday report, and Eliane wrote it down on her notebook. Hovey knows the probability he went from one place to another. Given the probability from Darnassus to Booty Bay be p, it means that if Hovey is at Darnassus today, the chance he is going to Booty Bay tomorrow is p. Eliane knows the probability of given place to be in given weather. Now given the first place, and the two probability matrices, can you help Hovey to figure out the route which has the greatest probablity.
Input
The first line is an integer T， the number of test cases.
In each test cases, the first is three positive integers n, m, w (1 ≤ n ≤ 1000, 1 ≤ m, w ≤ 100). Hovey has stayed in Azeroth for n + 1 days. Days are labeled from 0 to n. The number of places in Azeroth is m. The number of weather conditions in Azeroth is w. Hovey was always at Darnassus in day 0, which is place 0.
Then n integers follow, each is in the range of [0, w - 1]. They are weather conditions from day 1 to n.
Then m lines follow, each containing m numbers. The jth number in the ith line is the probabilty from place i to place j. Places are numbered from 0.
Then m lines follow, each containing w numbers. The jth number in the ith line is the probabilty that place i is in weather condition j. Weather conditions are numbered from 0.
In each test cases, the first is three positive integers n, m, w (1 ≤ n ≤ 1000, 1 ≤ m, w ≤ 100). Hovey has stayed in Azeroth for n + 1 days. Days are labeled from 0 to n. The number of places in Azeroth is m. The number of weather conditions in Azeroth is w. Hovey was always at Darnassus in day 0, which is place 0.
Then n integers follow, each is in the range of [0, w - 1]. They are weather conditions from day 1 to n.
Then m lines follow, each containing m numbers. The jth number in the ith line is the probabilty from place i to place j. Places are numbered from 0.
Then m lines follow, each containing w numbers. The jth number in the ith line is the probabilty that place i is in weather condition j. Weather conditions are numbered from 0.
Output
For each test cases, output n intergers in the range of [0, m - 1] in a line, seperated by a single space, representing the route which has the greatest probability. If there is a tie, output the one with the least lexicographic order, e.g. 2 1 3 is less than 2 3 1.
Sample Input
1 3 3 2 1 1 0 0.3 0.5 0.2 0.1 0.2 0.7 0.3 0.3 0.4 0.6 0.4 0.4 0.6 0.3 0.7
Sample Output
1 2 0