"Metro"#6081
Bunny McRabbit, mayor of Rabbitville, has decided that the city needs an underground metro system. The system will consist of a single line, which runs straight from one side of Rabbitville to the opposite side. There will be no bends of any kind, as the mayor insists.
Furthermore, there will be underground stations at a few precisely specified locations on the line. Each station will have a single street-level entrance located along the metro line (above the tunnel or beyond it, but always on the same line as the tunnel). Each entrance must not be too far from its station: the distance along the line between a station and its entrance can be at most (but it can be less, or even ).
Please help Mr. McRabbit choose locations for the entrances in such a way that the distances between any two consecutive station entrances will be the same.
We consider both metro stations and their entrances as points on the line containing the tunnel. The first line of the input contains two integers: , the total number of metro stations (2 \le n \le 1000), and , the maximum allowed distance between a station and its entrance (0 \le d \le 10\ 000).
The second line contains distinct integers in ascending order, with absolute values not exceeding 10^9. These are the coordinates of the first, second, ..., and last stations on the line.
Output integers — the coordinates of the entrances for the first, second, ..., and last metro stations, respectively. No two entrances can be located at the same point. If there are multiple solutions, output any of them. If there are no integral solutions, output 0.
Example 1