Cho đồ thị vô hướng, liên thông, có trọng số, gồm ~N~ đỉnh và ~N-1~ cạnh. Các đỉnh được đánh số từ ~1~ đến ~N~. Tất cả các cạnh ban đầu có trọng số bằng ~0~.

Người ta có ~M~ thao tác cập nhật thông tin trên cây cho bởi bộ ~4~ số ~\{A,B,C,D\}~ yêu cầu hãy tăng trọng số tất cả các cạnh trên đường đi từ ~A~ đến ~B~ lên ~1~ đơn vị, nhưng không được tăng trọng số các cạnh trên đường đi từ ~C~ đến ~D~ trong truy vấn đó.

Sau đó có ~Q~ câu hỏi cho bởi bộ ~2~ số ~\{E,F\}~ hãy tính tổng trọng số các cạnh trên đường đi ngắn nhất từ ~E~ đến ~F~.

Input

• Dòng đầu là số ~N, M, Q~ ~(1 \le N, M, Q \le 10^5)~.

• ~N-1~ dòng tiếp theo ghi các cặp ~(u,v)~ thể hiện cạnh của cây.

• ~M~ dòng tiếp theo ghi ~4~ số ~A,B,C,D~ với ~1 \le A,B,C,D \le N~ thể hiện yêu cầu cập nhật tăng trọng số cạnh.

• ~Q~ dòng tiếp theo ghi ~2~ số ~E,F~ ~(1 \le E,F \le N)~ thể hiện câu hỏi tính tổng.

Output

Ghi ra ~Q~ dòng tương ứng cho ~Q~ câu trả lời tính tổng.

Scoring

Sample Input 1

5 2 2
1 2
2 4
2 5
1 3
1 4 2 3
3 4 2 5
4 5
4 3

Sample Output 1

2
4

Notes

Sau ~2~ truy vấn cập nhật, các cạnh có trọng số là: ~(1,2)=1~; ~(1,3)=1~; ~(2,4)=2~; ~(2,5)=0~.