통행료

트럭 운송 회사가 내부 프로세스를 최적화하려 한다. 주된 목적은 비용 절감이다. 이 회사는 모든 도로마다 통행료를 내야 하는 지역에서 영업한다. 각 도로는 두 장소(도시, 마을 등)를 직접 연결한다. 회사에는 여러 주문이 들어오는데, 각 주문은 한 장소에서 다른 장소로 화물을 운반하라는 것이다. 주문을 처리할 때 회사는 전체 통행료를 최소로 내고 싶어 한다. 이 지역의 도로망은 각 간선에 비용(해당 도로의 통행료)이 있는 그래프로 모델링할 수 있으므로, 회사가 실제로 알고 싶은 것은 이 그래프에서 두 노드 사이의 최저 비용 경로의 비용이다.

그런데 이 지역의 도로망 그래프에는 흥미로운 성질이 있다. 방향 그래프이고(즉 모든 도로가 일방통행), 상수 $K$에 대해 $\lfloor b/K \rfloor = 1 + \lfloor a/K \rfloor$일 때만 $a$에서 $b$로 가는 간선이 있을 수 있다.

주어진 주문 목록의 각 주문마다 회사가 해당 주문을 처리하기 위해 내야 하는 최소 통행료를 출력하는 프로그램을 작성하시오.

첫째 줄에 네 정수 $K$(위에서 설명한 의미), $N$(장소의 수), $M$(도로의 수), $O$(주문의 수)가 주어진다.

다음 $M$개 줄에는 각각 세 정수 $a, b, t$가 주어진다($0 \le a, b < N$). 이는 $a$에서 $b$로 가는 일방통행 도로가 있고 통행료가 $t$임을 뜻한다. $\lfloor b/K \rfloor = 1 + \lfloor a/K \rfloor$가 성립하며, 두 장소를 하나 이상의 도로가 연결하지 않음이 보장된다.

마지막으로 $O$개 줄이 주어지며, 각 줄에는 두 정수 $a, b$가 있다. 이는 장소 $a$에서 장소 $b$로 화물을 운반하는 주문이 있음을 뜻한다.

출력은 $O$개 줄로 이루어지며, 각 줄에 정수 하나를 출력한다. $i$번째 줄에는 $i$번째 주문의 두 장소 사이 최저 비용 경로의 통행료를 출력한다. 그러한 경로가 없으면 그 줄에 $-1$을 출력한다.

항상 $1 \le N \le 50\,000$, $1 \le O \le 10\,000$, $K \le 5$이다. 또한 모든 주문 $a, b$에 대해 $0 \le a < b < N$이고, 모든 통행료 $t$에 대해 $1 \le t \le 10\,000$이다. 부분 문제의 입력에는 다음과 같은 추가 제한이 있다.