There is a country which consists of N cities named as 1,2,3......N . These cities are connected by N-1 bi-directional roads. And there is only one unique path to visit from one city to any other city.
As the name suggests the country suffers a lot from floods due to excessive rain and roads get submerged under water. The President of the country plans to improve transport by increasing the height of cities. Let the initial height of city i be denoted by Ai. The President selects Q pairs of cities and for every pair L and R, he approves to increase the height of each city falling on a simple path from L to R by x.
You have to print the final height of all cities.
Input:
First line of input is two integers N and Q representing total number of cities and total number of queries respectively.
Next N-1 lines have two integers U and V representing city U and city V are directly connected by a bi-directional road.
Next line contains N integers representing initial height of cities i.e., Ai (1 <= i <= N).
Next Q line contains 3 integers L R x meaning you have to add value x to height of all the cities lying on simple path from L to R ( both including ).
Output :
Print N integers representing height of cities.
Constraints :
1 <= N, Ai, x, Q <= 105
Note :
Please fill up this form if you want to be considered for onsite final round.
