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~.

Dữ liệu vào:

• Dòng đầu là số ~N~,~M~,~Q~ ~(1≤N,M,Q≤〖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≤A,B,C,D≤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≤E,F≤N)~ thể hiện câu hỏi tính tổng.

Kết quả ra:

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

Ví dụ:

Input

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

Output

2
4

Nguồn: chuyên Lào Cai