Có ~N~ thành phố trong vương quốc XYZ, được đánh số từ ~1~ đến ~N~. Các thành phố được nối bởi ~N - 1~ con đường hai chiều, các con đường được đánh số thứ tự từ ~1~, vương quốc XYZ coi như một đồ thị dạng cây (luôn có đường đi giữa mọi cặp thành phố).

Trên một số con đường có các trạm kiểm soát. Có tổng cộng ~M~ trạm, trạm thứ ~j~ nằm trên một con đường ~P_j~. Để đi qua trạm này, người đi phải trả: ~1~ đồng vàng hoặc ~C_j~ đồng bạc.

Có ~Q~ người, mỗi người có thông tin: Bắt đầu tại thành phố ~S_k~ muốn đi đến thành phố ~T_k~. Có ~X_k~ đồng vàng và ~Y_k~ đồng bạc.

Khi qua một trạm kiểm soát, người đó phải chọn một trong hai cách trả tiền (nếu đủ tiền). Mỗi người đều muốn giữ lại nhiều vàng nhất có thể sau khi hoàn thành hành trình.

Yêu cầu: Hãy trả lời với mỗi người, nếu không thể đi từ ~S_k~ đến ~T_k~, in ra ~-1~. Ngược lại, in ra số đồng vàng lớn nhất còn lại sau khi đi.

Input

• Dòng đầu ghi ba số ~N, M, Q~ ~(2 \le N \le 10^5;\ 1 \le M \le 10^5;\ 1 \le Q \le 10^5)~ là số thành phố, số trạm kiểm soát và số người dân.

• ~N - 1~ dòng tiếp theo: mỗi dòng chứa ~A_i, B_i~ thể hiện một con đường nối hai thành phố.

• ~M~ dòng tiếp theo, mỗi dòng chứa ~P_j, C_j~, trạm kiểm soát trên đường ~P_j~ với chi phí bạc ~C_j~.

• ~Q~ dòng tiếp theo: mỗi dòng chứa ~S_k, T_k, X_k, Y_k~.

Output

Gồm ~Q~ dòng trả lời cho mỗi hành trình của người dân tương ứng. Dòng thứ ~k~ ghi ra số vàng tối đa còn lại nếu đi được, in ra ~-1~ nếu không thể đi.

Scoring

Sample Input 1

5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

Sample Output 1

1
2
-1

Notes

Trong ví dụ trên, mỗi người sẽ đi theo đường duy nhất giữa hai thành phố và phải trả phí tại các trạm kiểm soát bằng vàng hoặc bạc sao cho tối ưu. Người thứ nhất đi từ ~3~ đến ~4~ qua các thành phố ~3 \rightarrow 1 \rightarrow 2 \rightarrow 4~, chọn trả ~1~ vàng và ~9~ bạc nên còn lại ~1~ vàng, đây là tối ưu. Người thứ hai đi từ ~5~ đến ~3~ theo đường ~5 \rightarrow 2 \rightarrow 1 \rightarrow 3~, trả ~2~ vàng và ~4~ bạc nên còn lại ~2~ vàng, không thể giữ nhiều hơn. Người thứ ba đi từ ~2~ đến ~3~ nhưng không đủ tiền để qua các trạm nên không thể hoàn thành hành trình, do đó kết quả là ~-1~.