HOJOBOROLO, a multinational company, has N employees numbered from 1 through N. Each employee, except for lower-level employees, has at least one subordinate. Lower-level employees  have no subordinate. Each employee, except for the head of the company, has exactly one direct  supervisor. The head of the company is a direct or indirect supervisor of all employees. Employee  number 1 is the head of the company and he is in the highest level. There are N teams in the  company and employee number i leads the i-th team. The i-th team consists of the team leader  (employee number i) and all the direct or indirect subordinates of the team leader. 
Now, there will be Q projects this year for the company. The head will distribute all the projects  among the teams. One project will not be given to more than one group. 
After completing a project, all the team members associated with the project will get a bonus  amount which will be added to their account. If employee number X is a team leader then he/she  will get a 2Y bonus amount and other team members will get a bonus amount of Y. 
You have to tell the final account balance for each employee at the end of this year.
 

There will be T(1 <= T <= 10 ) test cases. The second input line has an integer N(1 <= N <= 5x10^5  ) and Q (1<= Q <= N) - number of employees and the number of project. 
The third line contain N integers - a1,a2, . . . . ,aN (1≤ai≤10^3).Here ai denotes the Initial account  balance of Employee i. 
After this, there is (N-1) line. In each line there are 2 integers A ( 1 <= A <= N ) and B (1 <= B <=  N).A is the direct boss of B in the company that is B is the subordinate of A. 
Also there are Q lines.In each line there are 2 integers X ( 1 <= X <= N ) and Y (1<= Y <= 5000) - team leader for this project and bonus amount for each subordinates.
 

Print N integers: for each employee (1, 2, …….,N), final account balance they will get at the the end  of this year.

Input copy	Output copy
1 6 3 1000 1000 1000 1000 1000 1000 1 2 1 3 1 4 3 6 3 5 1 2000 4 3000 3 1500	5000 3000 6000 9000 4500 4500