Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2864
Catch the thief

Time Limit: 5 Seconds      Memory Limit: 32768 KB

The famous theif stole a valuable diamond in City S. He rushed to City T to leave this country as soon as he got the diamond. when he reach City T, he could fly to Country X where he would be safe.
You, a good policeman, are assigned to catch to theif. You have the map in this country, and you know that the theif will always choose the shortest way to escape.
Before you start up, your leader come to ask you how to catch the theif. You must tell him how many places can the theif be at the time your leader inquires.

Input

There are multiple cases. The first line of each test case contains four intergers, n, m, indicating the number of cities and roads in the country, S, T, the starting city and the target city, 1 ≤ S, T ≤ n ≤ 1000. The following m lines contain 3 intergers each, indicating the two ending cities of the road and the time to pass the road. The cities are numbered from 1 to n and the time will not exceed 10000. There is at most one road between any two cities. All the roads are bidirectional. There is at least a path from City S to City T. The next line contains an integer q, and q lines containing an integer which is the time your leader inquires follow. q will be a positive integer no larger than 1000, and the time inquired will be nonnegative intergers no larger than 10000000.The time the theif got the diamond is the referrence time.

Output

Each test case outputs q integers corresponding to the quries. Output a blank line between test cases.

Sample Input

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

Sample Output

1
2
1


Author: GUAN, Yao
Source: ZOJ Monthly, June 2007
Submit    Status