Hệ thống cấp nước của thành phố gồm ~N~ nút (được đánh số từ ~1~ đến ~N~) và ~N-1~ đường ống nối giữa các nút. Hệ thống này đảm bảo luôn có duy nhất một đường đi giữa hai nút bất kỳ (cấu trúc cây). Mỗi đường ống nối hai nút có hai thông số:

• Độ dài đường ống ~W~;

• Mã chất liệu ~C~ (là một số nguyên dương).

Thành phố cần đánh giá mức độ an toàn của việc vận chuyển nước giữa các trạm. Bạn nhận được ~Q~ truy vấn, mỗi truy vấn gồm ~4~ số nguyên ~(u, v, K, y)~ với ý nghĩa:

• Kiểm tra tuyến đường truyền nước đi từ nút ~u~ đến nút ~v~;

• Chất liệu tiêu chuẩn ưu tiên là ~y~;

• Ngưỡng chịu lỗi tối đa là ~K~.

Yêu cầu: Với mỗi truy vấn ~(u, v, K, y)~, gọi ~S~ là số lượng đường ống trên tuyến đường từ ~u~ đến ~v~ có chất liệu khác với chất liệu ưu tiên ~y~:

• Nếu ~S \le K~, hãy in ra tổng độ dài của tất cả các đường ống trên tuyến đường từ ~u~ đến ~v~.

• Nếu ~S > K~, in ra ~-1~.

Input

• Dòng ~1~ chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 10^5)~ là số nút và số lượng truy vấn;

• ~N-1~ dòng tiếp theo, mỗi dòng thứ ~i~ chứa ~4~ số nguyên ~u_i, v_i, W_i, C_i~ mô tả một đường ống nối giữa nút ~u_i~ và ~v_i~, có độ dài ~W_i~ và mã chất liệu ~C_i~ ~(1 \le u_i, v_i \le N; 1 \le W_i \le 10^9; 1 \le C_i \le 10^5)~;

• ~Q~ dòng tiếp theo, mỗi dòng chứa ~4~ số nguyên ~u, v, K, y~ mô tả một truy vấn, trong đó ~(1 \le u, v \le N; 0 \le K \le N; 1 \le y \le 10^5)~.

Output

Gồm ~Q~ dòng, mỗi dòng ghi một số nguyên là kết quả tương ứng với truy vấn theo thứ tự xuất hiện trong dữ liệu vào.

Scoring

Sample Input 1

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

Sample Output 1

12
-1
-1

Notes

Tuyến đường từ ~1~ đến ~4~ đi qua ~3~ đoạn ống: ~(1, 2)~ chất liệu ~1~; ~(2, 3)~ chất liệu ~2~; ~(3, 4)~ chất liệu ~1~.

Tổng độ dài toàn tuyến ~= 5 + 3 + 4 = 12~.

• Truy vấn ~1~: ~y = 1, K = 1~. Các đoạn ống có chất liệu khác ~1~ là đoạn ~(2, 3)~ ~\rightarrow~ số lượng ~= 1 \le 1~ (thỏa mãn). In ra tổng độ dài ~12~.

• Truy vấn ~2~: ~y = 1, K = 0~. Số lượng đoạn ống khác ~1~ vẫn là ~1 > 0~ (vi phạm). In ra ~-1~.

• Truy vấn ~3~: ~y = 3, K = 2~. Cả ~3~ đoạn ống đều khác chất liệu ~3~ ~\rightarrow~ số lượng ~= 3 > 2~ (vi phạm). In ra ~-1~.