"Метро"
Кролик МакРабит и мэр РабитВилли решили, что город нуждается в подземной системе метро. Система будет состоять из единственной линии, которая будет проходить прямо из одной части РабитВилли к противоположной части города. Мэр настоял на том, чтобы она не имела никаких изгибов. Подземные станции будут находиться в указанных местах на линии. Каждая станция будет иметь один вход на уровне улицы, расположенный вдоль линии метро (над туннелем или под ним, но в любом случае на одной линии с туннелем). Вход на станцию не может находиться далеко от самой станции. Расстояние по прямой от станции до входа в нее может быть не больше d (но может быть меньше, и даже равняться 0). Помогите МакРабиту выбрать положения входов таким образом, чтобы расстояния между любыми двумя входами в последовательные станции были одинаковыми.
Входные данные
Будем рассматривать станции метро и входы на них как точки на прямой, проходящей через туннель. Первая строка содержит два целых числа: количество станций метро n (2 ≤ n ≤ 1000) и максимальное расстояние d (0 ≤ d ≤ 10 000), на котором могут находиться станции и входы в них. Вторая строка содержит n различных целых чисел в возрастающем порядке, по модулю не превосходящих 10^9. Это координаты первой, второй, …, последней станции на прямой.
Выходные данные
Выведите n целых чисел - координаты входов на первую, вторую, …, последнюю станцию метро соответственно. Никакие два входа не могут находиться в одной точке. Если существует несколько решений, то вывести любое из них. Если целочисленных решений не существует, то вывести 0.