Description:
There are $$$n$$$ water tanks in a row, $$$i$$$-th of them contains $$$a_i$$$ liters of water. The tanks are numbered from $$$1$$$ to $$$n$$$ from left to right.
You can perform the following operation: choose some subsegment $$$[l, r]$$$ ($$$1\le l \le r \le n$$$), and redistribute water in tanks $$$l, l+1, \dots, r$$$ evenly. In other words, replace each of $$$a_l, a_{l+1}, \dots, a_r$$$ by $$$\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}$$$. For example, if for volumes $$$[1, 3, 6, 7]$$$ you choose $$$l = 2, r = 3$$$, new volumes of water will be $$$[1, 4.5, 4.5, 7]$$$. You can perform this operation any number of times.
What is the lexicographically smallest sequence of volumes of water that you can achieve?
As a reminder:
A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ of the same length if and only if the following holds: in the first (leftmost) position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.
Input Format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of water tanks.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — initial volumes of water in the water tanks, in liters.
Because of large input, reading input as doubles is not recommended.
Output Format:
Print the lexicographically smallest sequence you can get. In the $$$i$$$-th line print the final volume of water in the $$$i$$$-th tank.
Your answer is considered correct if the absolute or relative error of each $$$a_i$$$ does not exceed $$$10^{-9}$$$.
Formally, let your answer be $$$a_1, a_2, \dots, a_n$$$, and the jury's answer be $$$b_1, b_2, \dots, b_n$$$. Your answer is accepted if and only if $$$\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$$$ for each $$$i$$$.
Note:
In the first sample, you can get the sequence by applying the operation for subsegment $$$[1, 3]$$$.
In the second sample, you can't get any lexicographically smaller sequence.