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^5, 0 ≤ M ≤ 10^9)~.
• 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 Input

6 260000000
60 10 40 20 30
0 1
0 3
0 5
1 2
1 4

Sample Output

40000000
80000000
80000000
60000000

Sample Input

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

Sample Output

17
11
22