Bunny McRabbit, mayor of Rabbitville, has decided that the city needs an underground metro system. The system will consist of a single line and the line will go straight from one side of Rabbitville to the opposite side of the city. There will not be bends of any kind, 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 on the same line with the tunnel anyway). Entrance to the station cannot be too far from the station itself. In fact, distance along the line between a station and its entrance can be at most \textbf{d} (but can be less than that or even equal \textbf{0}). Please help Mr. McRabbit to choose locations for the entrances in such a way that distances between any two consecutive stations’ entrances will be the same. \InputFile We consider both metro stations and their entrances to be points on the line containing the tunnel. In the first line of the input there are two integers: \textbf{n}, the total number of metro stations (\textbf{2} ≤ \textbf{n} ≤ \textbf{1000}), and \textbf{d}, the maximum distance allowed between a station and its entrance (\textbf{0} ≤ \textbf{d} ≤ \textbf{10 000}). The second line of the input contains \textbf{n} distinct integers, in ascending order, with absolute values not exceeding \textbf{10^9}. These are the coordinates of the first, second, …, last stations on the line. \OutputFile Output \textbf{n} integers which are coordinates of entrances to the first, second, …, last metro stations respectively. No two entrances can be located at the same point. If there are multiple solutions, you can output any one of them. If there are no integral solutions, output \textbf{0}.