Tùng Dương có một cây (đồ thị vô hướng liên thông và không có chu trình) gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\). Dương đặt tên cây này là \(\textbf{cây Nhi}\). Mỗi cạnh của cây Nhi đều được tô một màu nào đó trong \(N-1\) màu có sẵn (các màu này được đánh mã từ \(1\) đến \(N-1\)). Cạnh thứ \(i\) của cây Nhi nối đỉnh \(u_i\) với đỉnh \(v_i\), đồng thời có độ dài \(d_i\) và được tô màu với mã màu là \(c_i\). Dương nhờ bạn lập trình trả lời \(Q\) truy vấn, trong đó, truy vấn thứ \(j\) cho biết bốn số nguyên \(x_j\), \(y_j\), \(u_j\), \(v_j\) và yêu cầu bạn cập nhật độ dài của tất cả các cạnh được tô màu với mã màu \(x_j\) thành \(y_j\), sau đó in ra khoảng cách giữa đỉnh \(u_j\) và đỉnh \(v_j\) (các thay đổi trên không được áp dụng cho các truy vấn tiếp theo).

Bạn hãy ra tay giúp đỡ Dương làm chủ được cây Nhi nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(2\leq N\leq 10^5\), \(1\leq Q\leq 10^5\)).

• Dòng thứ \(i\) trong \(N-1\) dòng tiếp theo chứa bốn số nguyên \(u_i\), \(v_i\), \(c_i\) và \(d_i\).

• Dòng thứ \(j\) trong \(Q\) dòng tiếp theo chứa bốn số nguyên \(x_j\), \(y_j\), \(u_j\) và \(v_j\).

Output

• In ra \(Q\) dòng là câu trả lời cho các truy vấn tương ứng.

Example

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4

130
200
60