Cho một cây có ~N~ đỉnh. Ban đầu đỉnh ~i~ có giá trị ~a_i~. Có ~Q~ truy vấn, mỗi truy vấn tăng tất cả các đỉnh nằm trên đường đi từ ~u~ đến ~v~ một lượng là ~x~. Hãy in ra giá trị của các đỉnh của cây sau khi xử lí hết truy vấn.

Input

Vào từ file UPDTREE.INP:

• Dòng đầu ghi số ~N\ (1 \le N \le 10^5)~ là số đỉnh của cây.
• Dòng tiếp theo ghi ~N~ là số ~a_1, a_2, \dots a_N~ ~(1 \le a_i \le 10^9)~ là giá trị ban đầu của các đỉnh.
• ~N-1~ dòng tiếp ghi bộ số ~u, v\ (1 \le u, v \le N)~ mô tả cạnh của cây.
• Dòng tiếp ghi số ~Q\ (1\le Q \le 10^5)~.
• ~Q~ dòng tiếp theo mô tả truy vấn, mỗi dòng chứa bộ số ~(u,v,x)~ thể hiện truy vấn.

Output

Ghi ra tệp UPDTREE.OUT:

• Ghi ra một dòng ~N~ số là giá trị tại các đỉnh sau khi thực hiện ~Q~ truy vấn.

Sample Input 1

5
0 0 0 0 0
1 2
1 3
2 4
2 5
2
4 5 2
3 5 1

Sample Output 1

1 3 1 2 3

Giải thích