There are $n$ people participating in a competition, and Xiaoduo is one of them. Here, $n$ is guaranteed to be a positive integer power of 2.

The $n$ participants are lined up, numbered $1, 2, \dots, n$ from left to right. The $i$-th person has an ability value $a_i$. When a person with ability $x$ duels a person with ability $y$, the probability that the former wins is $x/(x+y)$, and the probability that the latter wins is $y/(x+y)$.

The competition proceeds as follows:

• If only one person remains, that person is the final winner.
• Otherwise, the two people at the front of the queue, let them be A and B, have a duel. The loser of the duel leaves the competition, and the winner returns to the back of the queue.

Xiaoduo knows the ability values of everyone (including himself) and the order of the other $n-1$ people in the queue, but he does not know his own position in the queue. There are $n$ possible positions where he could be inserted into the queue of $n-1$ people. For each possibility, calculate the probability that Xiaoduo becomes the final winner.

Input

The first line contains two positive integers $n$ and $x$, representing the number of people and Xiaoduo's ability value, respectively.

The second line contains $n-1$ positive integers $a_1 \sim a_{n-1}$, describing the ability values of the participants in the queue (excluding Xiaoduo) from left to right.

Output

Output $n$ real numbers. The $i$-th number represents the probability of Xiaoduo winning if he is inserted between the $(i-1)$-th and $i$-th person in the queue (if $i=1$, he is inserted before the first person; if $i=n$, he is inserted after the $(n-1)$-th person).

Your output will be considered correct if the absolute error compared to the standard answer is within $10^{-9}$.

Examples

Input 1

4 2
1 1 1

Output 1

0.444444444444
0.444444444444
0.444444444444
0.444444444444

Note 1

Regardless of Xiaoduo's position, to win the competition, he needs to win two consecutive duels. In both duels, his opponent has an ability value of 1 and he has an ability value of 2, so the win probability is $2/3$. Thus, the final win probability is $(2/3)^2 = 4/9$.

Input 2

8 4
1 2 3 4 5 6 7

Output 2

0.202724628508
0.202724628508
0.168937190423
0.168937190423
0.098444548984
0.098444548984
0.088968603093
0.088968603093

Constraints

There are 10 test cases in this problem, each worth 10 points. All data satisfies $2 \le n \le 4096$, $1 \le x, a_i \le 10^4$, and there exists a positive integer $k$ such that $n=2^k$.

• Test cases 1 and 2 satisfy that all $a_i$ are the same.
• Test case 3 satisfies $n=4$.
• Test case 4 satisfies $n=8$.
• Test case 5 satisfies $n=32$.
• Test case 6 satisfies $n=256$.
• Test cases 7, 8, 9, and 10 have no special properties.