Cho một cây gồm \(n\) đỉnh có gốc 1. Đỉnh thứ \(i\) có nhẵn \(a_i\). Ban đầu các nhãn đều bằng 0. Có \(q\) truy vấn, mỗi truy vấn có dạng \(i\) \(x\) tăng tất cả các đỉnh trong cây con gốc \(i\) lên \(x\).

Yêu cầu: sau khi thực hiện \(q\) truy vấn. Tìm nhãn của mỗi đỉnh.

Input

• Dòng 1 chứa 2 số \(n,q (1≤n,q≤10^5)\).

• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) thể hiện cạnh nối \(u,v (1≤u,v≤n).\)

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) \(x (1≤i≤n,x≤10^9)\) mô tả một truy vấn.

Output

• In ra \(n\) số nguyên, số thứ \(i\) là nhãn của đỉnh \(i\) sau khi thự hiện \(q\) truy vấn.

Sample Input

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

Sample Output

1 1 3 3 3