1109 : Nearest Maintenance Point

Description

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.

Input

There will be at most 200 test cases. Each case begins with four integers n, m, s, q(2 ≤ n ≤ 10⁴, 1 ≤ m ≤ 5 × 10⁴, 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 u_i, v_i, w_i(1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 1000), denoting there is a road of length w_i which connects city u_i and v_i. 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.

Output

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

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

3
1
1 3

Hint

Source

Author

Staginner