# 1109 : Nearest Maintenance Point

Time Limit: 2 Sec Memory Limit: 128 Mb Submitted: 457 Solved: 79## 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^{4}, 1 ≤ *m* ≤ 5 × 10^{4}, 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 Input

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

## Sample Output

3 1 1 3

## Hint

## Author

Staginner