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_j,H_j,r_j)~ với ý nghĩa: Cần thuê một phòng có diện tích thuộc phạm vi ~[L_j,H_j]~ và có khoảng cách tới công ty không quá ~r_j~.

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 thỏa 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.

Input

• 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_j,H_j,r_j~ mô tả yêu cầu tổ chức của cuộc họp thứ ~j~.

Output

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 thỏa mãn yêu cầu tổ chức cuộc họp thứ ~j~ thì ghi -1.

Scoring

Trong tất cả các test:

• ~1 \le n,m,Q \le 10^5~;

• ~0 \le s_i,c_i \le 10^9~;

• ~1 \le L_j \le H_j \le 10^9~;

• ~1 \le r_j \le 10^{14}~;

• ~1 \le w \le 10^9~.

Sample 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

Sample Output 1

8
2
1
9
-1

Notes

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~; cuộc họp cuối không tồn tại hội trường thỏa mãn.