EIU Programming Practices and Exams

Công ty của Phúc đang thi công một dự án rất lớn. Dự án được chia thành nhiều dự án con, mỗi dự án con lại tiếp tục được chia nhỏ hơn thành các thành phần nhỏ hơn, được gọi chung là hạng mục. Mỗi hạng mục chiếm tỉ lệ chi phí nhất định trong hạng mục cha. Công ty định phân bổ M tỷ đồng cho dự án. Hãy tính số tiền mỗi hạng mục sẽ được phân bổ.

Input

Dòng đầu tiên là 2 số nguyên N, M là số hạng mục của dự án và số tiền được phân bổ. Dự án lớn chính là hạng mục 0. Các hạng mục được đánh số từ 0 đến N – 1 (2 ≤ N ≤ 10⁵, 0 ≤ M ≤ 10⁹)

Dòng tiếp theo gồm N – 1 số thực a_i là tỉ lệ % chi phí của hạng mục so với hạng mục cha (1 ≤ i < N). Dữ liệu đảm bảo là tổng tỉ lệ các hạng mục con của một hạng mục luôn bằng 100.

N – 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên a, b thể hiện hạng mục b là con hạng mục a

Output

Gồm n dòng, dòng thứ i là thể hiện chi phí của hạng mục i. Chi phí của mỗi hạng mục được làm tròn tới hàng đơn vị.

Example

Input:
6 500
40 100 30 60 70 
0 5
5 4
0 3
3 2
5 1

Output:
500
140
150
150
210
350