Gao

Time Limit: 2 Seconds
Memory Limit: 65536 KB

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*_{i} indicating 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.

- 0
- 0 -> 1
- 0 -> 2
- 0 -> 1 -> 3
- 0 -> 2 -> 3

Therefore, building 0 appears 5 times in the shortest paths, while building 1, 2 and 3
each appears 2, 2, 2 times.

Author:

**ZHUANG, Junyuan**
Contest:

**ZOJ Monthly, October 2010**
Submit
Status