Một công ty vận tải đường bộ muốn tối ưu hóa các quy trình nội bộ, mà chủ yếu là tiết kiệm tiền. Công ty hoạt động trong một vùng mà mỗi con đường đều thu phí. Mỗi con đường nối trực tiếp hai địa điểm, chẳng hạn như thành phố hoặc làng. Công ty xử lý một tập các đơn hàng; mỗi đơn hàng yêu cầu vận chuyển hàng hóa từ một địa điểm đến một địa điểm khác. Khi thực hiện một đơn hàng, công ty muốn trả tổng phí đường bộ nhỏ nhất. Vì mạng lưới đường bộ của vùng có thể được mô hình hóa bằng một đồ thị mà mỗi cạnh có một chi phí cụ thể, chính là phí của con đường tương ứng, điều công ty thực sự muốn biết là chi phí của đường đi rẻ nhất giữa hai đỉnh trong đồ thị này.

Tuy nhiên, đồ thị mạng lưới đường bộ của vùng có một tính chất thú vị: đây là đồ thị có hướng, tức là mọi con đường đều là đường một chiều, và chỉ có thể có cạnh từ \(a\) đến \(b\) nếu \(\left\lfloor b/K \right\rfloor = 1+\left\lfloor a/K \right\rfloor\), với một hằng số \(K\).

Hãy viết chương trình tính, với mỗi đơn hàng trong danh sách được cho, tổng phí đường bộ nhỏ nhất mà công ty phải trả để thực hiện đơn hàng đó.

Ảnh: Wikimedia Commons; CC-BY-SA-3.0.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(K\), \(N\), \(M\) và \(O\), trong đó \(K\) có ý nghĩa như trên, \(N\) là số địa điểm, \(M\) là số con đường và \(O\) là số đơn hàng.

Mỗi dòng trong \(M\) dòng tiếp theo chứa ba số nguyên \(a\), \(b\) và \(t\) (\(0 \le a,b < N\)), cho biết có một con đường một chiều từ \(a\) đến \(b\) với phí \(t\). Dữ liệu bảo đảm \(\left\lfloor b/K \right\rfloor = 1+\left\lfloor a/K \right\rfloor\) và không có hai địa điểm nào được nối bởi nhiều hơn một con đường.

Cuối cùng là \(O\) dòng, mỗi dòng chứa hai số nguyên \(a\) và \(b\), mô tả một đơn hàng vận chuyển hàng hóa từ địa điểm \(a\) đến địa điểm \(b\).

Dữ liệu ra

In ra \(O\) dòng, mỗi dòng chứa một số nguyên. Dòng thứ \(i\) ghi tổng phí trên đường đi rẻ nhất giữa hai địa điểm của đơn hàng thứ \(i\). Nếu không tồn tại đường đi như vậy, in ra \(-1\) trên dòng đó.

Ràng buộc

• \(1 \le N \le 50\,000\).
• \(1 \le O \le 10\,000\).
• \(K \le 5\).
• Với mọi đơn hàng \((a,b)\), \(0 \le a < b < N\).
• Với mọi con đường có phí \(t\), \(1 \le t \le 10\,000\).
• Với mọi con đường từ \(a\) đến \(b\), \(0 \le a,b < N\) và \(\left\lfloor b/K \right\rfloor = 1+\left\lfloor a/K \right\rfloor\).
• Không có hai địa điểm nào được nối bởi nhiều hơn một con đường.

Phân nhóm

Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.

• Nhóm 1 (7 điểm): \(K=1\).
• Nhóm 2 (10 điểm): Mọi đơn hàng đều có \(a=0\).
• Nhóm 3 (8 điểm): \(O \le 100\).
• Nhóm 4 (31 điểm): \(O \le 3\,000\).
• Nhóm 5 (44 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13

15
9
7
8
-1

Nguồn

Baltic Olympiad in Informatics 2017, ngày thi thứ 1.