Mạng cấp nước

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

Dữ liệu vào

• 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$.

Dữ liệu ra

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.

Ràng buộc

• $1\le N,Q\le {10}^5$
• $1\le W_i\le {10}^9$, $1\le C_i\le {10}^5$
• $0\le K\le N$, $1\le y\le {10}^5$

Subtasks

• Subtask 1 ($30\%$ số điểm): $N,Q\le 1000$.
• Subtask 2 ($30\%$ số điểm): $N,Q\le {10}^5$; cây có dạng một đường thẳng (bậc của mỗi đỉnh không quá $2$).
• Subtask 3 ($40\%$ số điểm): $N,Q\le {10}^5$; cây có cấu trúc bất kỳ.

Ví dụ