Alternative Mart Batch 컴파일 명령

민식이는 OJUZ 시에서 자취하고 있다. OJUZ 시는 $N$개의 지역과 $M$개의 양방향 도로로 이루어져 있으며 $N$개의 지역 중 $K$개의 지역에는 할인마트가 위치해있다. 특정한 두 지역을 직접 연결하는 도로는 최대 하나 있으며 모든 도로의 두 끝 지역은 다르다. 또한 임의의 지역에서 다른 지역으로 가는 방법이 항상 존재한다.

민식이는 자기 일과가 끝나면 할인마트로 가서 요리재료와 간식거리를 산 후 자취방에 돌아온다. 민식이는 꽤 똑똑하기 때문에 항상 가장 빠른 길로 할인마트에 가서 물건을 산다. 허나, 어떤 경우에는 몇 개의 할인마트가 문을 닫을 때가 있다. 할인마트가 문을 닫으면 기존에 민식이가 가던 방법이 무용지물이 될 수 있다. 민식이는 자신이 자주 가던 할인마트가 문을 닫으면 어떤 할인마트로 가야 하는지 몰라 난감해한다.

민식이를 도와 매 순간 어떤 할인마트로 가야 하는지 구하는 프로그램을 작성하여라. 단, 민식이가 할인마트에서 집까지 가는 시간은 무시한다.

입력 형식

첫 번째 줄에는 지역의 수 $N$, 도로의 수 $M$, 할인마트의 수 $K$, 질의의 수 $Q$가 주어진다.

$(2 ≤ N ≤ 50,000, N-1 ≤ M ≤ 80,000, 1 ≤ K ≤ N, 1 ≤ Q ≤ 50,000)$

두 번째 줄에는 $K$개의 할인마트들이 위치한 지역의 번호가 오름차순으로 주어진다.

세 번째 줄부터 $M$개의 줄에는 도로의 두 끝점 $P_{i}$, $Q_{i}$와 도로의 길이 $V_{i}$가 주어진다.

$(1 ≤ P_{i}, Q_{i} ≤ N, 1 ≤ V_{i} ≤ 10,000)$

$M$+3번째 줄부터 $Q$개의 줄에는 민식이의 질의가 주어진다.

각 질의별로 민식이의 출발 지역 $S$와 문을 닫는 할인마트의 수 $X$, 그리고 문을 닫는 할인마트가 있는 지역의 번호 $C_{1}$, …, $C_{X}$가 주어진다.$(0 ≤ X ≤ min(10, K-1), 1 ≤ S, C_{i} ≤ N)$

출력 형식

$Q$개의 줄에 걸쳐, 민식이가 가야 하는 할인마트의 번호(할인마트가 위치한 지역의 번호)와 그때 민식이가 할인마트를 가는 최소 시간을 출력한다. 가장 빨리 갈 수 있는 할인마트가 여러 개라면 번호가 가장 작은 것을 출력한다.

입력과 출력의 예