EIU Programming Practices and Exams

Trong hệ thống kinh doanh đa cấp, người đầu tiên mở nhánh mới sẽ là node 0 (cấp 0), người này sẽ giới thiệu những người khác vào hệ thống hình thành cấp 1, mỗi người cấp i giới thiệu thêm người khác vào hệ thống hình thành cấp i+1. Kết quả ta có sơ đồ cây đa cấp. Khi một người bán được hàng thì những cấp giới thiệu trên sẽ nhận được hoa hồng theo tỉ lệ nhất định:

1. Cấp 1: Người trực tiếp bán sản phẩm, được hoa hồng bằng 15% doanh số bán hàng
2. Cấp 2: Người giới thiệu người bán Cấp 1 vào hệ thống, được hoa hồng bằng 1/2 hoa hồng của người bán Cấp 1
3. Cấp n: Người giới thiệu người bán Cấp (n-1) vào hệ thống, được hoa hồng bằng 1/2 hoa hồng của người bán Cấp (n-1)

Hoa hồng chỉ lấy phần nguyên

VD: 10*15% = 1.5 ta chỉ lấy 1

VD2: Người cấp 1 bán hàng nhận hoa hồng là 3, vậy người 2 nhận 3/2 = 1 (bỏ 0.5 không phải số nguyên).

Input

Dòng đầu tiên là số người trong công ty (1<=n<=10^5)

Dòng thứ 2 gồm n số nguyên k là doanh thu bán hàng của họ (số thứ i là doanh thu của người i, 1<= k<=10^5 )

N-1 dòng tiếp theo là người u và v, trong đó u là người giới thiệu v vào công ty.

Output

N dòng gồm id người của công ty và hoa hồng của người đó (cách nhau bởi khoảng trắng, sắp xếp theo ID tăng dần)

Example

Input:
10
4703 5434 5057 3109 7096 5881 8710 2022 6052 9187 
0 1
0 2
1 3
1 4
2 5
2 6
4 7
4 8
5 9

Output:
0 2744
1 1882
2 2196
3 466
4 1668
5 1571
6 1306
7 303
8 907
9 1378