Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

probabilities

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Game of Chance

time limit per test

6 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputThe King wants to marry off his daughter, and he wants her husband to have the greatest innate luckiness possible. To find such a person he decided to hold a heads-or-tails tournament.

If person $$$A$$$ with luckiness $$$x$$$ and person $$$B$$$ with luckiness $$$y$$$ play heads-or-tails against each other, person $$$A$$$ wins with probability $$$x/(x+y)$$$.

The tournament has several rounds. Each round some participants are split into pairs. Each pair plays against each other, and the loser leaves the tournament.

The participants are numbered from $$$1$$$ to $$$n$$$. During the first round, a number $$$k$$$ ($$$1 \le k \le n$$$) is selected such that $$$n-k/2$$$ is a power of $$$2$$$ (such $$$k$$$ always exists and is unique). Only participants numbered from $$$1$$$ to $$$k$$$ take part in the first round. It ensures that in all other rounds the number of participants is the power of $$$2$$$.

During other rounds, all the participants who still have not left the tournament take part. If during some round, participants numbered $$$p_1 < \ldots < p_{2m}$$$ take part, then they are split into pairs in the following manner: participant $$$p_{2i-1}$$$ plays against participant $$$p_{2i}$$$ for each $$$i$$$ from $$$1$$$ to $$$m$$$.

The rounds are held until only one participant is left. He is declared the winner of the tournament and he will marry the King's daughter. The princess can't wait to find out who is her future husband. She asked every participant to tell her his luckiness. Assuming they did not lie, she wants to know the probability of each participant winning the tournament. As you are the best friend of the princess, she asks you to help her.

Input

The first line of the input contains the number of participants, $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$). The second line of the input contains $$$n$$$ integer numbers, $$$a_1, \ldots, a_{n}$$$ ($$$1 \le a_i \le 10^9$$$). The luckiness of the $$$i$$$-th participant equals to $$$a_i$$$.

Output

Print $$$n$$$ numbers $$$p_i$$$. The $$$i$$$-th number should be the probability of the $$$i$$$-th participant winning the tournament. The absolute error of your answer must not exceed $$$10^{-9}$$$.

Example

Input

5 1 4 1 1 4

Output

0.026 0.3584 0.0676 0.0616 0.4864

Note

Here is an example of a tournament bracket, showing the winning probability in each pair.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2024 04:22:47 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|