Cây thông

Ông già Noel có một cây thông khổng lồ để trang hoàng cho đêm Giáng sinh. Trên các cành của cây thông, ông treo $N$ tấm thiệp trang trí được đánh số từ $1$ đến $N$. Tấm thiệp $i$ $(1\le i\le N)$ có độ lấp lánh được biểu thị bằng số nguyên không âm $A_i$. Các tấm thiệp được kết nối với nhau bằng $N-1$ đoạn dây. Đoạn dây thứ $i$ kết nối hai tấm thiệp $u_i$ và $v_i$ $(1\le u_i,v_i\le N)$. Hệ thống dây đảm bảo rằng giữa hai tấm thiệp bất kỳ trên cây luôn tồn tại duy nhất một đường đi trực tiếp kết nối hai tấm thiệp và các đoạn dây. Nói cách khác, các tấm thiệp và các đoạn dây tạo thành một đồ thị dạng cây có $N$ đỉnh và $N-1$ cạnh.

Mỗi thời điểm trong đêm Giáng sinh, ông già Noel sẽ thực hiện một phép thuật. Có $Q$ thời điểm lần lượt xảy ra đánh số từ $1$ đến $Q$. Tại thời điểm $t$ $(1\le t\le Q)$, ông thực hiện một phép thuật được mô tả bằng ba số nguyên dương $x_t,y_t,w_t$ với ý nghĩa: gán $A_v=A_v\%w_t$ với mọi tấm thiệp $v$ nằm trên đường kết nối từ tấm thiệp $x_t$ đến tấm thiệp $y_t$ (bao gồm cả $x_t$ và $y_t$). Sau khi thực hiện phép thuật, ông định nghĩa độ đẹp của cây tại thời điểm $t$ là tổng độ đẹp của các tấm thiệp trên cây tại thời điểm đó, tức là: $(A_1\%t)+(A_2\%t)+\dots +(A_N\%t)$. Nhắc lại, $\%$ là phép toán chia lấy dư.

Yêu cầu: Hãy giúp ông già Noel tính độ đẹp của cây sau mỗi lần thực hiện phép thuật.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $N$ và $Q$ $(1\le N,Q\le 2\times {10}^5)$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$ $(0\le A_i\le 2\times {10}^5)$.
• Dòng thứ $i$ trong số $N-1$ dòng tiếp theo chứa hai số nguyên dương phân biệt $u_i$ và $v_i$ mô tả một đoạn dây kết nối trực tiếp hai tấm thiệp $u_i$ và $v_i$ trên cây $(1\le u_i,v_i\le N)$.
• Dòng thứ $t$ trong số $Q$ dòng tiếp theo chứa ba số nguyên dương $x_t,y_t,w_t$ mô tả một lần thực hiện phép thuật tại thời điểm $t$ $(1\le x_t,y_t\le N;w_t\le 2\times {10}^5)$.
• Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Gồm $Q$ dòng, dòng thứ $t$ chứa một số nguyên là độ đẹp của cây sau khi thực hiện phép thuật tại thời điểm $t$.

Ràng buộc

• $1\le N,Q\le 2\times {10}^5$.
• $0\le A_i\le 2\times {10}^5$.
• $1\le u_i,v_i\le N$, $u_i\ne v_i$; các đoạn dây tạo thành một cây.
• $1\le x_t,y_t\le N$; $1\le w_t\le 2\times {10}^5$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $N,Q\le 5000$.
• Subtask 2 ($20\%$ số điểm): $A_v\le 2$, có dây nối trực tiếp giữa tấm thiệp $v$ và $v+1$ với mọi $v=1,2,\dots ,N-1$.
• Subtask 3 ($20\%$ số điểm): $x_t=y_t$ với mọi $t=1,2,\dots ,Q$, có dây nối trực tiếp giữa tấm thiệp $v$ và $v+1$ với mọi $v=1,2,\dots ,N-1$.
• Subtask 4 ($20\%$ số điểm): Có dây nối trực tiếp giữa tấm thiệp $v$ và $v+1$ với mọi $v=1,2,\dots ,N-1$.
• Subtask 5 ($20\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ