Дивний сон#474

Дивний сон

1 секунда
256 мегабайтів
Легка

Невідомим чином Козак Вус опинився на нескінченній числовій прямій у координаті . Протягом секунд, кожної секунди (1 \leq i \leq n) відбувалося наступне:

Зверніть увагу, що він ніколи не може опинитися у від'ємній координаті.

Прокинувшись, Козак Вус зрозумів, що це був сон: він чітко пам'ятає всі y_i та тривалість сну , але не може згадати, у якій координаті опинявся наприкінці кожної секунди. Заспокойте Козака Вуса й допоможіть відновити цей дивний сон!

Вхідні дані

Перший рядок містить два цілі числа та (1 \leq n \leq 2 \cdot 10^5; 0 \leq x \leq 10^4) — тривалість дивного сну і початкова координата Козака Вуса відповідно.

Другий рядок містить цілих чисел y_1, y_2, \dots, y_n (1 \leq y_i \leq 10^4), де y_i — число, яке Козак Вус бачив на початку -ої секунди сну.

Вихідні дані

Виведіть цілих чисел c_1, c_2, \dots, c_n, де c_i — координата, у якій опинявся Козак Вус наприкінці -ої секунди сну.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому прикладі Козак Вус починає з координати .

  • На початку першої секунди Козак Вус бачить число y_1=2. Найближчою координатою до кратною є . Тому наприкінці першої секунди Козак Вус залишиться у координаті .

  • На початку другої секунди Козак Вус бачить число y_2=4. Найближчими координатами до кратними є та . Оскільки 0<4, то наприкінці другої секунди Козак Вус опиниться у координаті .

  • На початку третьої секунди Козак Вус бачить число y_3=1. Найближчою координатою до кратною є . Тому наприкінці третьої секунди Козак Вус залишиться у координаті .

У другому прикладі Козак Вус починає з координати .

  • На початку першої секунди Козак Вус бачить число y_1=2. Найближчими координатами до кратними є та . Оскільки 4<6, то наприкінці першої секунди Козак Вус опиниться у координаті .

  • На початку другої секунди Козак Вус бачить число y_2=3. Найближчою координатою до кратною є . Тому наприкінці другої секунди Козак Вус залишиться у координаті .

  • На початку третьої секунди Козак Вус бачить число y_3=2. Найближчими координатами до кратними є та . Оскільки 2<4, то наприкінці третьої секунди Козак Вус опиниться у координаті .

У третьому прикладі Козак Вус починає з координати 10^4.

  • На початку першої секунди Козак Вус бачить число y_1=5001. Найближчою координатою до кратною є . Тому наприкінці першої секунди Козак Вус опиниться у координаті .

Оцінювання

Ви отримаєте не менше балів, якщо ваш розв'язок буде коректно працювати для n=1.

Ви отримаєте не менше балів, якщо ваш розв'язок буде коректно працювати для n \leq 2.

Ви отримаєте не менше балів, якщо ваш розв'язок буде коректно працювати для n \leq 100 та max(y_1,y_2, \ldots, y_n) \leq 100.