택시 2 (Taxis 2)
시간 제한4초메모리 제한1024 MB
붉은 택시(1엔)와 푸른 택시(반값 내림)를 타며 1번 마을에서 출발해 항상 1엔 이상을 유지하고 목표 마을에 도착하는 데 필요한 최소 초기 금액을 각 질의마다 구하고, L을 넘으면 Large를 출력한다.
문제
IOI 나라에는 1부터 N까지 번호가 붙은 N개의 도시와 1부터 M까지 번호가 붙은 M개의 도로가 있다.
각 도로는 택시로만 통행할 수 있다. 도로 i (1 ≦ i ≦ M)의 택시는 도시 Ai와 도시 Bi를 양방향으로 이동할 수 있고, 그 택시의 색은 Ci = 1일 때 빨간색, Ci = 2일 때 파란색이다. 택시에는 요금이 붙어, 타면 다음과 같이 소지금이 변한다.
- 타기 전의 소지금을
a엔이라고 한다. - 택시가 빨간색이면 탄 후의 소지금이
a - 1엔이 된다. - 택시가 파란색이면 탄 후의 소지금이
a ÷ 2를 정수로 내림한 값엔이 된다.
당신은 IOI 나라의 도시 1에 살고 있으며, 다음 Q개의 질문에 대한 답을 알고 싶어 한다. j번째 (1 ≦ j ≦ Q) 질문은 다음과 같다.
- 도시
1에서 출발해,1엔 이상의 소지금을 남긴 상태로 도시Tj에 도착하려면 처음에 최소 몇 엔의 소지금을 가지고 있어야 하는가. 단, 답이L엔보다 크면 대신Large라고 답한다.
도시와 택시의 정보, 그리고 질문의 내용이 주어졌을 때, 모든 질문에 답하는 프로그램을 작성하시오.
입력
입력은 다음 형식으로 표준 입력에서 주어진다.
N M Q L
A1 B1 C1
A2 B2 C2
:
AM BM CM
T1
T2
:
TQ
출력
표준 출력에 Q행을 출력하시오. j행째 (1 ≦ j ≦ Q)에는 j번째 질문의 답을 출력하시오.
제한
2 ≦ N ≦ 200 000.N - 1 ≦ M ≦ 200 000.1 ≦ Q ≦ 200 000.1 ≦ L ≦ 1 000 000 000.1 ≦ Ai ＜ Bi ≦ N(1 ≦ i ≦ M).(Ai, Bi) ≠ (Aj, Bj)(1 ≦ i ＜ j ≦ M).1 ≦ Ci ≦ 2(1 ≦ i ≦ M).2 ≦ Tj ≦ N(1 ≦ j ≦ Q).- 어떤 두 도시 사이든 여러 도로를 거쳐 오갈 수 있다.
- 입력되는 값은 모두 정수이다.