Có \(n\) thành phố được kết nối với nhau bởi \(n-1\) con đường, các thành phố đảm bảo liên thông với nhau. Mỗi thành phố \(u\) có một nhà trẻ và có \(a_u\) trẻ em trong đó.

An có \(x\) cái kẹo và xuất phát từ thành phố \(s\) di chuyển đến thành phố \(t\) theo đường đi ngắn nhất, với mỗi thành phố An đi qua (tính cả thành phố bắt đầu), An đến nhà trẻ và phát kẹo cho các trẻ em ở đó, An sẽ phát nhiều nhất có thể tại thời điểm đó và các trẻ em tại cùng một nhà trẻ phải được phát cùng một số lượng kẹo, tất nhiên có thể sẽ dẫn tới có nhà trẻ mà trẻ em ở đây không nhận được bất kì cái kẹo nào.

Yêu cầu:

• Hãy cho biết khi kết thúc hành trình thì An còn bao nhiêu cái kẹo.

• Cho \(q\) truy vấn, mỗi truy vấn tương ứng với bộ ba \((s,t,x)\) hãy đưa ra số kẹo còn lại.

Input

• Dòng đầu chứa \(n,q (1≤n,q≤2×10^5)\)

• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u,v\) mô tả cạnh nối giứa hai thành phố \(u,v\)

• Dòng tiếp theo chứa \(n\) số \(a_i (1≤a_i≤10^9 ).\)

• \(q\) dòng tiếp theo, mỗi dòng chứa ba số \(s,t,x (1≤s,t≤n;1≤x≤10^9)\) tương ứng với các truy vấn.

Output

• Ứng với mỗi truy vấn đưa ra kết quả trên một dòng.

Ràng buộc

• Subtask 1 :(20p): \(n,q≤2000\)

• Subtask 2 :(20p): cây có dạng đường thẳng từ 1 đến \(n; a_i≤100\)

• Subtask 3 :(20p): cây có dạng đường thẳng từ 1 đến \(n\)

• Subtask 4: (20p): \(t=1\)

• Subtask 5: (20p): không có ràng buộc gì thêm.

Sample Input

4 3
1 2
2 3
3 4
5 2 7 4
1 1 9
2 3 11
3 2 11

Sample Output

4
1
0