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