Back to the Himalayas

As the deer finds cold spring water, so do I find the money on top of the mountains! - Jany MooRANDy

It’s been so long since your favorite bomber Jany MooRANDy has been in the Himalayan Mountains and his enemies started questioning his abilities to make money. But have no worries, he’s back to the Himalayas to once again prove his claim: "Let the wind and rain blow, I make money in the Himalayas too! Where I make money packages, the enemies only collect stones!". After getting his PhD in physics proving that he has TDI brain he got to rename "the law of conservation of energy"to "the law of conservation of value".

It reads like this: the kinetic value of an object is equal to $(m \cdot v^2)/2$ (where $m$ is the mass of the object and $v$ is its velocity) and the potential value of an object is equal to $m \cdot g \cdot h$ (where $m$ is the mass of the object, $g$ is the gravitational acceleration which we will consider to be $10$, and $h$ is the difference of elevation between it and a reference point).

As we all know, the Himalayas are made up of $N$ peaks placed in a line, the $i^{th}$ peak having an elevation of $H_i$. Now Jany MooRANDy wants to collect the money which the previously built stop points for the Himalayas cable car have made (there is a cable car stop in every peak). Starting from a peak $i$ he will only go to the right (i.e. $i + 1, i + 2, ..., N$).

Having loads of value, he will be on his journey with a kinetic value equal to $(m \cdot v^2)/2$ right from the beginning. When jumping from the ith peak to the $(i + 1)^{th}$ peak he will either lose or gain value. If $H_i > H_{i+1}$ then he will gain $m \cdot g \cdot (H_i - H_{i+1})$ value, otherwise he will lose $m \cdot g \cdot (H_{i+1} - H_i)$ value. Over the course of the journey, his value cannot drop below $0$. Now, because he wants to make money packets he is wondering for every starting peak which is the farthest peak that he can go to?

Input

The first line contains three integers: $N (1 ≤ N ≤ 5 \cdot 10^5), m (1 ≤ m ≤ 10^{50})$ and $v (1 ≤ v ≤ 4 \cdot 10^4)$ – the number of peaks, Jany MooRANDy’s mass and speed respectively.
The second line contains $N$ integers, representing the $H$ array - the height of each peak. $(1 ≤ H_i ≤ 10^9)$.

For tests worth $30$ points, ($1 ≤ N ≤ 1 \ 000$), $m$ ($1 ≤ m ≤ 10^9$) and $v$ ($1 ≤ v ≤ 400$) hold.
For tests worth extra $30$ points, ($1 ≤ N ≤ 1 \ 000$), $m$ ($1 ≤ m ≤ 10^{50}$) and $v$ ($1 ≤ v ≤ 4 \cdot 10^4$) hold.

Note that previous knowledge of the physics concepts presented is not required and the task is solvable using the given assumptions and definitions from the statement.

Output

The output will consist of one line, having $N$ integers, separated by a space: $ans_1, ans_2, ..., ans_n$ where $ans_i$ is the index of the farthest peak Jany MooRANDy can reach starting from peak $i$.

Example

stdin

9 2 7
3 2 1 5 3 3 8 2 1

stdout

6 3 3 6 6 6 9 9 9

Explanation

Let’s see why $ans_1 = 6$
He starts from the first peak with kinetic value of $(2 \cdot 72)/2 = 49$, so his current value is $49$.

From peak $1$ to peak $2$, his value increases by $m \cdot g \cdot (H_1 − H_2) = 2 \cdot 10 \cdot 1 = 20$, so his current value becomes 69.
From peak $2$ to peak $3$, his value increases by $m \cdot g \cdot (H_2 − H_3) = 2 \cdot 10 \cdot 1 = 20$, so his current value becomes 89.
From peak $3$ to peak $4$, his value decreases by $m \cdot g \cdot (H_4 − H_3) = 2 \cdot 10 \cdot 4 = 80$, so his current value becomes 9.
From peak $4$ to peak $5$, his value increases by $m \cdot g \cdot (H_4 − H_5) = 2 \cdot 10 \cdot 2 = 40$, so his current value becomes 49.
From peak $5$ to peak $6$, his value decreases by $m \cdot g \cdot (H_5 − H_6) = 2 \cdot 10 \cdot 0 = 0$, so his current value stays the same.
From peak $6$ to peak $7$, his value decreases by $m \cdot g \cdot (H_7 − H_6) = 2 \cdot 10 \cdot 5 = 100$, so his current value would drop to $49 − 100 = −51$ which is below $0$ so he can’t go to peak $7$.
The farthest peak he can reach from peak $1$ is peak $6$.