Problem A
Bank robbery

You are a police in a city where banks are being robbed all the time. The roads in your city can be modeled as a connected graph with $n \leq 2 \cdot 10^5$ intersections, and $m \leq 2 \cdot 10^5$ bidirectional roads between intersections. There are police stations in exactly $k \leq 10000$ of the intersections. In a year, $r \leq 10^5$ banks are robbed, and being the head of the police you want to find out for each robbery which police station is the closest to the bank being robbed, so you can send a car there as fast as possible.

For each of the robberies $1, 2, ..., r$, find which police station is closest to the bank being robbed, and how far away it is. If multiple police stations are at the same distance, output the one with the lowest index.

It is guaranteed that you can get between any pair of intersections in the city using the roads. It is also guaranteed that there is at most one police station in each intersection.

Input

In the first line there are four integers $n \leq 10^5$, $m \leq 10^5$, $1 \leq k \leq 10000$ and $1 \leq r \leq 10^5$.

Then follow $m$ lines, each containing two integers $0 \leq a < n$ and $0 \leq b < n$, indicating that there is a road between intersection $i$ and $j$.

Then follow $k$ more lines, each containing an integer $p_ i < n$ indicating that police station number $i$ is in intersection $p_ i$.

Then follow $r$ more lines, each containing an integer $b_ i < n$ indicating that the $i^{th}$ robbery is in a bank in intersection $b_ i$.

Output

Output $r$ lines, each containing two integers $d$ and $b$, the distance from the bank to the police station which is the closest and the index of that police station. If multiple police stations are the same distance from the bank, you should output the one with the lowest index.

3 2 1 3
0 1
1 2
0
0
1
2

0 0
1 0
2 0

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

0 0
1 0
2 0
1 1
2 0
0 1

8 12 2 3
0 1
1 2
1 3
2 4
2 5
5 6
5 7
2 6
0 3
0 4
0 7
4 7
0
1
3
2
5

1 0
1 1
2 0