Công ty XYZ có \(n\) nhân viên, được tổ chức theo mô hình phân cấp dạng cây, với giám đốc là nhân viên số \(1\). Mỗi nhân viên (ngoại trừ giám đốc) có một quản lý trực tiếp. Ban đầu, tất cả nhân viên đều có hiệu suất làm việc bằng \(0\).

Công ty có một số chính sách khuyến khích năng suất làm việc như sau:

Có \(q\) đợt khuyến khích, trong mỗi đợt, tất cả các nhân viên trong cùng một nhóm (bao gồm quản lý và tất cả nhân viên cấp dưới của người đó) sẽ được tăng hiệu suất làm việc thêm một số điểm cố định. Nhiệm vụ của bạn là giúp công ty tính toán hiệu suất làm việc của từng nhân viên sau khi tất cả các đợt khuyến khích đã được áp dụng.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n,q\) \((1 \le n,q \le 10^5)\) — số lượng nhân viên và số lượng truy vấn.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \le u,v \le n, u \neq v)\), biểu diễn rằng nhân viên \(u\) và \(v\) có quan hệ trực tiếp (quản lý và nhân viên).
• Tiếp theo là \(q\) dòng, mỗi dòng chứa hai số nguyên \(u\) và \(x\), với \(u\) là mã số của nhân viên quản lý, và \(x\) là số điểm hiệu suất tăng thêm cho nhân viên đó cùng tất cả cấp dưới của họ trong đợt khuyến khích. \((1 \le x \le 10^9)\)

Dữ liệu ra

• In ra \(n\) số nguyên, tương ứng với hiệu suất làm việc của từng nhân viên từ \(1\) đến \(n\) sau khi tất cả các đợt khuyến khích đã được áp dụng.

Input 1

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

Output 1

1 1 3 3 3

Input 2

10 2
1 2
2 3
3 4
1 5
2 6
4 7
7 8
2 9
8 10
7 5
2 6

Output 2

0 6 6 6 0 6 11 11 6 11