Невідомим чином Козак Вус опинився на нескінченній числовій прямій у координаті . Протягом секунд, кожної секунди (1 \leq i \leq n) відбувалося наступне:
на початку -ої секунди він бачив деяке число y_i.
наприкінці -ої секунди він опинявся у найближчій координаті, яка є кратною y_i (тобто, координаті, що націло ділиться на y_i). Якщо таких координат декілька, він опинявся у найменшій з них.
Зверніть увагу, що він ніколи не може опинитися у від'ємній координаті.
Прокинувшись, Козак Вус зрозумів, що це був сон: він чітко пам'ятає всі 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 — координата, у якій опинявся Козак Вус наприкінці -ої секунди сну.
Example 1
Example 2
Example 3
У першому прикладі Козак Вус починає з координати .
На початку першої секунди Козак Вус бачить число 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.