Sau khi đính hôn với Hoàng tử, hàng ngày cô Tấm và Hoàng tử hẹn gặp nhau để bàn về kế hoạch tổ chức đám cưới. Bản đồ giao thông của vương quốc 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. Hệ thống giao thông đảm bảo có đường đi từ \(1\) tới \(n\).

Nhà của Tấm ở địa điểm \(1\) còn hoàng cung, nơi hoàng tử ở là đị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 (tại thời điểm \(0\)) 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 hai người có thể gặp nhau tại thời điểm sớm 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\), Tấm đi mỗi km mất \(a_j\) giây và Hoàng tử đi mỗi km mất \(b_j\) giây. Hãy cho biết \(c_j\) là thời điểm sớm nhất hai người có thể gặp nhau trong ngày thứ \(j\). (\(\forall j = 1,2,\ldots,k\))

Input

• Dòng đầu chứa ba số nguyên \(n\), \(m\), \(k\) (\(2 \leq n \leq 10^5\); \(1 \leq m \leq 2\cdot10^5\); \(1 \leq k \leq 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 \leq u_i, v_i \leq n\); \(1 \leq w_i \leq 10^6\))
• \(k\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(a_j\), \(b_j\) (\(1 \leq a_i, b_i \leq 10^6\))

Output

• Ghi ra \(k\) số nguyên \(c_1, c_2,\ldots,c_k\) mỗi số trên một dòng.

Example

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

28
6