EIU Programming Practices and Exams

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á P0 đồ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á Pi đồ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á Li đồ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 <=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 <= 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 <=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
Output:
1 2 1 1 0