Ô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 ≤ i ≤ 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 ≤ u_i, v_i ≤ 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 ≤ t ≤ 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) + ... + (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.

Input

Vào từ file văn bản PINE.INP:

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~ (~1 ≤ N, Q ≤ 2 \times 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~0 ≤ A_i ≤ 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 ≤ u_i, v_i ≤ 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 ≤ x_t, y_t ≤ N; w_t ≤ 2 \times 10^5~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản PINE.OUT:

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

Sample Input

5 3
2 1 4 4 8
1 2
2 3
3 4
4 5
1 5 5
1 5 3
3 3 1

Sample Output

0
3
4

• Ở thời điểm ~t = 1~, dãy ~A~ là ~(2, 1, 4, 4, 3)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (4~ ~\%~ ~t) + (4~ ~\%~ ~t) + (3~ ~\%~ ~t) = 0~.
• Ở thời điểm ~t = 2~, dãy ~A~ là ~(2, 1, 1, 1, 0)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (1~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) = 3~.
• Ở thời điểm ~t = 3~, dãy ~A~ là ~(2, 1, 0, 1, 0)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) = 4~.

Subtasks