Trong một mạng kinh doanh đa cấp X, người đầu tiên mở nhánh mới sẽ là node ~0~ (cấp ~0~).

• Người này mua hàng trực tiếp từ nhà sản xuất với giá ~P_0~ đồng, và bán lại hàng cho những người ở cấp ~1~ với giá cao hơn giá mua vào vào ~10\%~.
• Người ở cấp thứ ~i~ ~(i > 0)~ mua hàng của người cấp ~i-1~, với giá ~P_i~ đồng, và bán cho người cấp ~i+1~ với giá cao hơn giá mua vào ~10\%~ (làm tròn xuống, tới hàng đơn vị).
• Tuy nhiên, người mua ở cấp ~i~ ~(i > 0)~ có quyền quyết định mua hàng nếu giá không vượt quá ~L_i~ đồng.
• Mỗi người đều biết tổng số người trong nhánh của mình, họ nhập một lượng hàng bằng tổng số người trong nhánh - kể cả bản thân họ. Nếu không bán được hàng, họ phải sử dụng tất cả sản phẩm còn lại.
• Em hãy giúp tính mỗi người phải sử dụng bao nhiêu sản phẩm.

Input

• Dòng đầu tiên gồm ~1~ số nguyên ~n~, là số người trong mạng kinh doanh đa cấp X ~(n \le 10^5)~
• ~n – 1~ dòng tiếp theo gồm ~2~ số nguyên ~a~, ~b~, thể hiện ~a~ là người bán hàng cho ~b~ hoặc ~b~ là người bán hàng cho ~a~ ~(0 \le a, b < n)~
• Dòng tiếp theo gồm ~n~ số nguyên ~L_i~ là mức giá cao nhất người ~i~ có thể mua sản phẩm.
• Dòng cuối cùng gồm số nguyên ~P~ là giá người đầu tiên mua sản phẩm từ nhà sản xuất ~(P \le 10^{10})~.

Output

• ~1~ dòng gồm ~n~ số nguyên ~t_i~, là số sản phẩm người ~i~ phải sử dụng.

Example Input

5
0 1
1 2
0 3
1 4
150 120 121 110  110
100

Example Output

1 2 1 1 0