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:

• 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
• 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~
• 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)~
• Lưu ý: Hoa hồng chỉ lấy phần nguyên
  • VD: ~10 \times 15\% = 1.5~ ta chỉ lấy ~1~
  • VD: 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 \le n \leq 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 \le k \le 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

Example Output

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