Internet Trouble

The government is bringing internet service to people in remote areas, in this case small towns that grew along a long, busy highway. $N$ towns sit side by side along the highway, and each town takes up exactly one kilometer of it. The towns are numbered 1 to $N$ in order along the highway.

To provide the service, the government builds access point stations with satellite links. Each station goes in a different town, and building one station costs $B$. The government wants the service to be as good as possible, so every house is connected directly to one of these stations. Connecting a house in town $i$ to a station in town $j$ costs $|i - j| \times C$, where $C$ is the price of one kilometer of cable. Cable used inside a town is cheap enough to ignore, so a house in the town that holds the station it connects to pays no cable cost.

Given $N$, $B$, $C$ and the number of houses in each town, write a program that computes the minimum total cost of connecting every house in every town, counting both the stations and the cable. The government has not fixed the number of stations yet, so compute the minimum cost for 1, 2, $\dots$, $N$ stations.

The first line contains three integers $N$, $B$ and $C$ separated by spaces: the number of towns, the cost of building one access point station, and the price of one kilometer of cable ($1 \le N \le 6000$, $1 \le B \le 10^9$, $1 \le C \le 100$).

The second line contains $N$ integers $H_1, H_2, \dots, H_N$ separated by spaces, where $H_i$ is the number of houses in town $i$ ($1 \le H_i \le 10^9$).

Print $N$ integers on one line, separated by single spaces: the minimum total cost of connecting every house when 1, 2, $\dots$, $N$ access point stations are built.