Description

Who is cpcs? Every one in ZJU ACM-ICPC team knows him. Although he has been graduated from ZJU, he is still active in ZOJ and many contests. cpcs is the legendary figure in ZJU ACM-ICPC history. It is not only because he has passed nearly all the problems on ZOJ, but also because his very famous function name "gao" which is now widely spreaded and used by many ACMers.

"gao" in Chinese means to do something but it's not that formal in grammar. So it is usually used verbally. In addition, "gao" can be explained as a spirit, a belief, even an attitude to life, which makes cpcs use "gao" as most of the function names (Of course there should be some functions named such as "main" in C or C++).

One day, cpcs got a map of the city he lived in. There were N buildings (numbered from 0 to N - 1) in the map with the building he was in marked as 0. Between the buildings, there were some unidirectional roads. He then wrote a program with function "gao" that could calculate all the shortest paths from building 0 to all the building. Here, there might be more than one shortest paths to a building. Now he wanted to know, for each query of buildings, how many shortest paths that he figured out with function "gao" passed through the queried building. Note that if a building is unreachable from building 0, no shortest path would passes through it.

Input

There are multiple test cases. For each case, the first line is three numbers N, M, Q (1 ≤ Q ≤ N ≤ 10000, 1 ≤ M ≤ 50000) indicating the number of buildings, the number of roads and the number of queries. Next is M lines each containing three numbers a, b, d (0 ≤ a, b < N, 0 < d ≤ 200) indicating that there is a road of length d from building a to building b. Next is Q lines each containing one integer q_iindicating a query to a building. Most cases are small, no more than 5 large cases.

Output

In each case, for each query, you should print one line with the number of shortest paths that pass through the building. Since the answer may be very large, you only need to print the last 10 digits of the answer.

Sample Input

4 4 4
0 1 2
0 2 2
1 3 1
2 3 1
0
1
2
3

Sample Output

0000000005
0000000002
0000000002
0000000002

Hint

In the sample, there are 5 shortest paths.