В одном из купе поезда Эркюль Пуаро нашел записку с некоторым набором чисел. Также на окне черной краской обнаружилось аккуратно выведенное число R.
Эркюль предположил, что записка — это некоторая последовательность чисел, к которой была применена функция«шума» c коэффициентом R. То есть к каждому числу первоначальной последовательности было прибавлено случайное число из диапазона [ - R;R]. Результат же как раз и был записан на найденной записке.
Восстановить исходную последовательность не представляется возможным, однако, Пуаро хочет понять, какое наибольшее количество различных чисел могло в ней быть. Помогите ему решить эту задачу!
В первой строке содержатся два числа n и R — количество чисел в записке и число, написанное на стекле, соответственно (1 ≤ n ≤ 105, 1 ≤ R ≤ 109).
В следующей строке содержатся n чисел ai — числа из найденной записки ( - 109 ≤ ai ≤ 109).
В первой строке выведите одно число — наибольшее возможное количество различных чисел в первоначальной последовательности.
В следующей строке выведите n целых чисел bi — элементы последовательности (|ai - bi| ≤ R). Если подходящих ответов несколько, выведите любой из них.
5 2
1 2 3 4 5
5
1 2 3 4 5
3 1
1 1 1
3
0 1 2