EIU Programming Practices and Exams

Năm nay công ty KP đạt lợi nhuận cao nên quyết định thưởng cho các đơn vị và nhân viên. Công ty được tổ chức theo mô hình cây với KP là gốc, các node trong là phòng ban, và node lá là nhân viên. KP sẽ thưởng cho các đơn vị và nhân viên mà KP trực tiếp quản lý, tiếp theo các đơn vị sẽ chia thưởng cho các đơn vị con và nhân viên mà đơn vị đó quản lý. Tiền thưởng được chia tỉ lệ thuận với điểm đánh giá của nhân viên và đơn vị.

Ví dụ: KP quản lý đơn vị A, và 2 nhân viên B, và C; có điểm đánh giá lần lượt là 60, 40, 30. KP có tổng tiền thưởng là 260 triệu đồng. A, B, C nhận được lần lượt là 120 triệu, 80 triệu, 60 triệu.

Cho mô hình công ty của KP và tổng số tiền thưởng, hãy cho biết mỗi nhân viên được nhận bao nhiều tiền.

Input

Dòng đầu tiên là 2 số nguyên N, M là số nhân viên/đơn vị trong công ty và số tổng tiền thưởng. KP được đánh số 0. Nhân viên và đơn vị được đánh được đánh số từ 1 đến N – 1 (2 ≤ N ≤ 10⁵, 0 ≤ M ≤ 10⁹).

Dòng tiếp theo gồm N – 1 số thực a_i là điểm đánh giá của nhân viên/đơn vị thứ i (1 ≤ i < N).

N – 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên a, b thể hiện a là quản lý của b.

Output

Với mỗi nhân viên theo thứ tự tăng dần, hãy cho biết tiền thưởng họ nhận. Số tiền được làm tròn đến hàng đơn vị.

Sample