JOI 국가의 행사

JOI 국에는 $N$개의 도시가 있으며, 도시들은 $M$개의 양방향 도로로 연결되어 있다. 모든 도시는 서로 연결되어 있어 어떤 도시에서 다른 어떤 도시로도 이동할 수 있다.

현재 $K$개의 도시에서 축제가 열리고 있다. 축제를 싫어하는 사람 $Q$명이 각자 출발 도시에서 도착 도시로 이동하려 한다. 어떤 도시에서 축제까지의 거리는, 그 도시에서 가장 가까운 축제 도시까지의 최단 경로 길이로 정의한다.

각 사람은 이동 경로를 자유롭게 고를 수 있다. 하나의 경로가 주어지면 그 경로 위 도시들 각각의 '축제까지의 거리' 중 가장 작은 값을 그 경로의 값이라 하자. 우리는 이 값이 최대가 되도록 경로를 고르고 싶다. 각 사람에 대해, 선택할 수 있는 경로들의 값 중 최댓값을 구하여라. 출발 도시와 도착 도시도 경로에 포함된다.

첫째 줄에 도시의 수 $N$, 도로의 수 $M$, 축제가 열리는 도시의 수 $K$, 축제를 싫어하는 사람의 수 $Q$가 공백으로 구분되어 주어진다.

이어지는 $M$개의 줄에는 각 도로의 정보가 출발 도시, 도착 도시, 거리 순으로 공백으로 구분되어 주어진다. 거리는 $1$ 이상 $1000$ 이하이다.

이어지는 $K$개의 줄에는 축제가 열리는 도시의 번호가 한 줄에 하나씩 주어진다. 축제가 열리는 도시의 번호는 서로 중복되지 않는다.

이어지는 $Q$개의 줄에는 각 사람의 출발 도시와 도착 도시가 한 줄에 하나씩 공백으로 구분되어 주어진다. 출발 도시와 도착 도시는 서로 다르다.

$Q$개의 줄에 걸쳐, 입력된 순서대로 각 사람이 얻을 수 있는 값(경로 위 도시들의 '축제까지의 거리' 중 최솟값을 최대화한 값)을 출력한다.

• $2 \le N \le 100,000$
• $1 \le M \le 200,000$
• $1 \le K \le N$
• $1 \le Q \le 100,000$

아래 그림은 예시에 등장하는 도로망을 나타낸다. 그림 1은 첫 번째 예시, 그림 2는 두 번째 예시의 도로망이다.