Thành phố nơi Cường làm việc có \(n\) địa điểm, được đánh số từ \(1\) đến \(n\). Một số địa điểm trong thành phố có hội trường cho thuê. Hội trường ở địa điểm thứ \(i\) có diện tích là \(s_i\) và giá thuê là \(c_i\) (quy ước rằng nếu ở địa điểm \(i\) không có hội trường thì \(s_i = c_i = 0\)). Có \(m\) con đường hai chiều, mỗi con đường nối giữa hai địa điểm và có độ dài cho trước. Hệ thống đường bảo đảm việc đi lại giữa mọi địa điểm.

Công ty của Cường ở địa điểm \(1\). Theo kế hoạch, có \(Q\) cuộc họp cần được tổ chức trong các ngày tới. Do thời gian tổ chức và quy mô khác nhau nên mỗi cuộc họp đều có yêu cầu riêng về việc tổ chức. Yêu cầu tổ chức của cuộc họp thứ \(j\) được mô tả bởi ba số nguyên \((L_i, H_i, r_i)\) với ý nghĩa: Cần thuê một phòng có diện tích thuộc phạm vi \([L_i, H_i]\) và có khoảng cách tới công ty không quá \(r_i\).

Yêu cầu

Với mỗi cuộc họp, hãy giúp Cường tìm hội trường có giá thuê rẻ nhất mà vẫn thoả mãn yêu cầu tổ chức. Biết rằng các cuộc họp này có thời gian tổ chức khác nhau nên có thể nhiều cuộc họp cùng thuê một hội trường.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(Q\).
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa hai số nguyên \(s_i\), \(c_i\).
• Mỗi dòng trong số \(m\) dòng tiếp theo chứa ba số nguyên \(u\), \(v\), \(w\) cho biết có một con đường độ dài \(w\) nối giữa hai địa điểm \(u\) và \(v\).
• Dòng thứ \(j\) trong số \(Q\) dòng tiếp theo chứa ba số nguyên \(L_i\), \(H_i\), \(r_i\) mô tả yêu cầu tổ chức cuộc họp thứ \(j\).

Dữ liệu ra

• Ghi \(Q\) dòng. Dòng thứ \(j\) là giá thuê hội trường rẻ nhất cho cuộc họp thứ \(j\), nếu không có hội trường nào thoả mãn yêu cầu tổ chức cuộc họp thứ \(j\) thì ghi \(-1\).

Input 1

6 6 5
4 9
1 8
3 9
0 0
6 2
3 1
1 2 2
2 3 3
1 4 1
4 5 1
5 3 2
2 6 4
1 3 4
3 6 2
3 6 6
3 6 1
5 5 6

Output 1

8
2
1
9
-1

Giải thích:

• Các hội trường có thể thuê cho 5 cuộc họp lần lượt nằm ở các địa điểm: 2, 5, 6, 1, và không tồn tại hội trường phù hợp cho cuộc họp thứ 5.

Ràng buộc:

• Trong tất cả các test:
  • \(1 \leq n, m, Q \leq 10^5\)
  • \(0 \leq s_i, c_i \leq 10^9\)
  • \(1 \leq L_i \leq H_i \leq 10^9\)
  • \(1 \leq r_i \leq 10^{14}\)
  • \(1 \leq w \leq 10^9\)
• Có 16% số test với \(n \le 100\);
• Có 24% số test với \(Q \le 100\);
• Có 28% số test với \(rⱼ = 10^{14}\) với mọi \(j = 1, 2, ..., Q\);
• Có 32% số test với ràng buộc gốc.