D. Money Game
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Putata and Budada are organizing a game with $$$n$$$ players. Each player has some deposit, which is a real number. Player $$$i$$$ has $$$a_i$$$ deposits in the beginning. During each round of the game, the followings happen in order:

  • Player $$$1$$$ gives player $$$2$$$ half of player $$$1$$$'s deposit.
  • Player $$$2$$$ gives player $$$3$$$ half of player $$$2$$$'s deposit.
  • ...
  • Player $$$n-1$$$ gives player $$$n$$$ half of player $$$n-1$$$'s deposit.
  • Player $$$n$$$ gives player $$$1$$$ half of player $$$n$$$'s deposit.

The $$$n$$$ players played this game for exactly $$$2022^{1204}$$$ rounds. Putata wonders how much deposit each player has after the game. Please write a program to answer his question.

Input

The first line contains an integer $$$n$$$ ($$$2\leq n\leq 10^5$$$), denoting the number of players.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i \leq 10^6$$$), denoting the deposit player $$$i$$$ has in the beginning.

Output

Output one line with $$$n$$$ real numbers, denoting the deposit each player has after they played this game.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer will be considered correct if $$$\frac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$$$.

Example
Input
2
4 2
Output
4.00 2.00
Note

During one round, the deposit they have changed as follows: $$$[4,2]\to [2,4] \to [4,2]$$$. Their deposit does not change after this round, so the answer is the same as the input.