CSG-CPC Online Judge

1109 : Nearest Maintenance Point

         Time Limit: 2 Sec     Memory Limit: 128 Mb     Submitted: 457     Solved: 79    


A county consists of n cities (labeled 1, 2, …, n) connected by some bidirectional roads. Each road connects a pair of distinct cities. A robot company has built maintenance points in some cities. Now, they need your help to write a program to query the nearest maintenance point to a specific city.


There will be at most 200 test cases. Each case begins with four integers n, m, s, q(2 ≤ n ≤ 104, 1 ≤ m ≤ 5 × 104, 1 ≤ s ≤ min {n, 1000}, 1 ≤ q ≤ min {n, 1000}), the number of cities, the number of roads, the number of cities which have maintenance points and the number of queries. Then m lines contain the descriptions of roads. Each of them contains three integers ui, vi, wi(1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 1000), denoting there is a road of length wi which connects city ui and vi. The next line contains s integers, denoting the cities which have maintenance points. Then q lines contain the descriptions of queries. Each of them contains one integer denoting a specific city. The size of the whole input file does not exceed 6MB.


For each query, print the nearest city which has a maintenance point. If there are multiple such cities, print all of them in increasing order separated by a single space. It is guaranteed that there will be at least one such city.

Sample Input

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

Sample Output

1 3