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

• на початку ~i~-ої секунди він бачив деяке число ~y_i~.

• наприкінці ~i~-ої секунди він опинявся у найближчій координаті, яка є кратною ~y_i~ (тобто, координаті, що націло ділиться на ~y_i~). Якщо таких координат декілька, він опинявся у найменшій з них.

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

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

Input

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

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

Output

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

Sample Input 1

3 2
2 4 1

Sample Output 1

2 0 0

Sample Input 2

3 5
2 3 2

Sample Output 2

4 3 2

Sample Input 3

1 10000
5001

Sample Output 3

10002

Notes

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

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

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

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

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

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

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

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

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

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

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

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

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