The COS galaxy is located at the edge of the universe and is a desolate place. Although humans have developed the ability to perform space jumps, the only ones interested in visiting this place are physicists attempting to explore the mysteries of the universe. Professor H is one such great physicist.

After 20 years of observation and calculation, Professor H discovered that the COS galaxy consists of $n$ planets, numbered from $1$ to $n$. These $n$ planets and the spaceship Professor H is traveling in are all on a straight line, and the planets are all on one side of the spaceship. The distances between the planets and the spaceship form an arithmetic progression: planet 1 is at a distance of 1 unit from the spaceship, planet 2 is at a distance of 2 units, ..., and planet $n$ is at a distance of $n$ units.

Professor H is attempting to study the forces acting on the planets. Through his observations, he found that planet $j$ is acted upon by planet $i$ if and only if $i \le \alpha j$. In this case, the magnitude of the force exerted by planet $i$ on planet $j$ is: $F_{i\to j}=\dfrac{m_i m_j}{j-i}$

Here, $\alpha$ is the COS constant, which is always very small. Intuitively, each planet is only affected by planets that are far away. Professor H has already counted the number of planets $n$ and estimated the COS constant $\alpha$ and the mass $m_i$ of each planet. He hopes you can help him calculate the total force acting on each planet. He knows his data is not perfectly precise, so he does not require your results to be perfectly accurate; a relative error of no more than 5% is acceptable.

Input

The first line of the input file contains the number of planets $n$ and the COS constant $\alpha$, separated by a space. This is followed by $n$ lines, each containing an integer $m_i$, representing the mass of the $i$-th planet.

The input data satisfies $1 \le n \le 10^5$, $0<\alpha\le 0.35$, and $0 \le m_i \le 10^7$ for each $i$.

Output

Lines 1 through $n$ should each contain a real number, representing the total force acting on the corresponding planet.

Examples

Input 1

5 0.3
3
5
6
2
4

Output 1

0.000000
0.000000
0.000000
1.968750
2.976000

Note

The exact results should be 0 0 0 2 3. However, since the error here does not exceed 5%, it is considered correct.