Cho một hệ thống giao thông gồm n địa điểm đánh số từ 1 tới n và m con đường hai chiều đánh số từ 1 tới m. Con đường thứ i nối giữa hai địa điểm ~u_i~, ~v_i~ và có độ dài ~w_i~ km (or miles). Hệ thống giao thông đảm bảo có đường đi từ 1 tới n. Thuận và Đông là hai người bạn thân, Thuận ở địa điểm 1 và Đông ở địa điểm n. Hàng ngày họ muốn gặp nhau ở một địa điểm nào đó trong n địa điểm đã cho. Khi đã xác định điểm hẹn, hai người sẽ xuất phát cùng lúc, mỗi người đi từ nhà mình tới điểm hẹn theo con đường ngắn nhất. Người đến điểm hẹn trước sẽ phải chờ người đến sau. Với mỗi ngày, tùy theo phương tiện giao thông mà họ lựa chọn, bạn được cho biết tốc độ di chuyển của từng người. Hãy xác định điểm hẹn cho cuộc gặp gỡ ngày hôm đó sao cho thời gian chờ đợi của người đến trước là nhỏ nhất. Yêu cầu: Bạn cần tìm giải pháp cho k ngày (đánh số từ 1 tới k). Trong ngày thứ j, Thuận đi mỗi km mất ~a_j~ giây và Đông đi mỗi km mất ~b_j~ giây. Hãy cho biết ~c_j~ là thời gian chờ đợi (tính bằng giây) của người tới điểm hẹn trước trong ngày thứ j. (∀j=1,2,…,k)

Dữ liệu vào:

• Dòng 1 chứa 3 số nguyên n,m,k (2 ≤ n ≤ ~10^5~;1 ≤ m ≤ 2.~10^5~;1 ≤ k ≤ ~10^5~)
• m dòng tiếp theo, dòng thứ i chứa ba số nguyên ~u_i~,~v_i~,~w_i~ (1≤~u_i~,~v_i~≤n;1≤~w_i~≤~10^6~)
• k dòng tiếp theo, dòng thứ j chứa hai số nguyên ~a_j~,~b_j~ (1 ≤ ~a_i~,~b_i~≤~10^6~)

Kết quả: Ghi ra k số nguyên ~c_1~,~c_2~,…,~c_k~ mỗi số trên một dòng.

Ví dụ:

INPUT

6 6 2
1 2 1
1 5 6
2 3 2
3 4 3
4 6 4
5 6 5
7 4
5 5

OUTPUT

7
5

Giải thích:

• Ngày 1: Hai người hẹn gặp ở điểm 3, Thuận đi mất 21 giây và Đông đi mất 28 giây, Thuận phải chờ 7 giây
• Ngày 2: Hai người hẹn gặp ở điểm 5, Thuận đi mất 30 giây và Đông đi mất 25 giây, Đông phải chờ 5 giây