A tournament organizer records an entire single-elimination bracket as a binary tree: the root node is the final match, and every match node may have up to two children representing the two matches that fed into it (a semifinal feeds the final, a quarterfinal feeds a semifinal, and so on). Each match node stores an integer crowd-noise reading taken during that match.

For every round of the bracket — starting at the final (the root) and moving outward to earlier rounds — report the average crowd-noise reading of all matches played in that round.

Input format

Line 1: a single integer n (1 ≤ n ≤ 10000) — the number of tokens describing the bracket. Line 2: n space-separated tokens giving the bracket in level order (breadth-first, root first): each token is either an integer match reading or the literal word null marking a match that does not exist (a bye). The first token is always a real match (never null). A null token has no children of its own, and once every real match at the deepest recorded round has been listed, any of its unlisted children are implicitly treated as null.

Output format

Print one line with the average crowd-noise reading of each round, in order from the final outward, separated by single spaces. Print every average with exactly 5 digits after the decimal point.

Constraints

• 1 ≤ n ≤ 10000
• Every crowd-noise reading is an integer with -10000 ≤ reading ≤ 10000
• The first token is never null

7
5 9 20 null null 15 7

5.00000 14.50000 11.00000

1
3

3.00000