Tối ưu chi phí

Một công ty vận tải đang cố gắng tối ưu hóa chi phí bằng cách tìm đường đi rẻ nhất để vận chuyển hàng giữa các địa điểm. Khu vực mà công ty hoạt động có hệ thống đường một chiều, mỗi con đường đều phải trả phí (gọi là toll).

Mỗi con đường nối trực tiếp 2 địa điểm \(a\) và \(b\) (với \(a < b\)), và thỏa mãn điều kiện đặc biệt: \(b \div K = a \div K + 1\)
với \(K\) là một hằng số cho trước. Ký hiệu \(\div\) là phép chia lấy nguyên (div).

Cho danh sách các con đường có phí và danh sách các đơn hàng cần vận chuyển giữa hai địa điểm, hãy giúp công ty tính chi phí thấp nhất để thực hiện từng đơn hàng. Nếu không thể đi từ \(a\) đến \(b\), hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa 4 số nguyên \(K, N, M, O\) (\(1 \le N \le 5 \cdot 10^4\), \(1 \le O \le 10^4\), \(K \le 5\))
• Mỗi dòng trong \(M\) dòng tiếp theo chứa 3 số nguyên \(a, b, t\) (\(0 \le a < b < N\), \(1 \le t \le 10^4\)) --- có đường một chiều từ \(a\) đến \(b\) với phí \(t\), thỏa mãn $
  b \div K = a \div K + 1
  $
• Mỗi dòng trong \(O\) dòng tiếp theo chứa hai số nguyên \(a, b\) (\(0 \le a < b < N\)) --- mô tả một đơn hàng cần vận chuyển từ \(a\) đến \(b\)

Output

In ra \(O\) dòng, dòng thứ \(i\) là chi phí tối thiểu để đi từ \(a\) đến \(b\) của đơn hàng thứ \(i\). Nếu không thể đi, in -1.

Scoring

• Subtask 1 (10 điểm): \(K = 1\)
• Subtask 2 (13 điểm): Tất cả đơn hàng có \(a = 0\)
• Subtask 3 (15 điểm): \(O \le 100\)
• Subtask 4 (30 điểm): \(O \le 3000\)
• Subtask 5 (32 điểm): Không giới hạn gì thêm

Example

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