{"code":"tkpc07tree","name":"Cây Nhi","description":"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). \r\n\r\nBạn hãy ra tay giúp đỡ Dương làm chủ được cây Nhi nhé!\r\n\r\n

Input

\r\n\r\n- 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$).\r\n\r\n- 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$.\r\n\r\n- 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$.\r\n\r\n

Output

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 5 3\r\n 1 2 1 10\r\n 1 3 2 20\r\n 2 4 4 30\r\n 5 2 1 40\r\n 1 100 1 4\r\n 1 100 1 5\r\n 3 1000 3 4\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 130\r\n 200\r\n 60\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Cây Nhi đã cho được minh họa bằng hình dưới đây, với màu đỏ tượng trưng cho mã màu $1$, màu xanh lá cây tượng trưng cho mã màu $2$ và nét đứt tượng trưng cho mã màu $4$:\r\n\r\n ![enter image description here][1]\r\n\r\n\r\n [1]: https://i.ibb.co/kKQ2wYY/colorfultree.png","points":500.0,"partial":true,"time_limit":2.5,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}