Phuc made for his girlfriend a shelf that has many floors with rose pots on them. On a raining day, he wonders what will happen If he pours standing water in the top pots down to the bottom pots, how much water will the bottom pots contain?

Note that:

• Because of different design, size and position, water from one upper pot can only be poured down to some certain lower pots, lower pots only receive water from one upper pot
• If there are more than ~1~ pot below, he divides the amount of water of the upper pot equally to all lower pots.
• If there is no pots below, he writes down the amount of standing water in that pot.
• The uppermost pot is numbered with ~0~.

Input

• First line is the number of pots ~N~ ~(1 \le N \le 10^5)~
• Second line has ~N~ integers ~K_i~, each denotes the amount of water in ~i^{th}~ pot ~(1 \le K \le 10^5)~
• ~N-1~ next lines each has two integers ~u~ and ~v~, which means pot ~u~ receives water from pot ~v~ ~(u,v < n)~

Output

• With each pot (ordered by increasing id) containing water, print out on one line the id and the amount of water in it, The amount of water is rounded to the fourth decimal number

Example Input

5
16 3 4 2 1
1 0
2 0
3 2
4 2

Example Output

1 11.0
3 8.0
4 7.0