eolymp
bolt
Try our new interface for solving problems
Məsələlər

Загублені біти

Загублені біти

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Костя полюбляє всі натуральні числа, але гарні числа – його найулюбленіші. Гарними числами він вважає числа, які націло діляться на k.

Одного разу Костя побачив в крамниці гарне натуральне число n. Йому воно так сподобалося, що він вирішив його купити та подарувати своїй мамі. Але коли Костя прийшов додому він побачив, що десь загубив деякі біти цього числа і воно стало негарним числом m. Допоможіть йому відновити деякі біти, щоб число знову стало гарним. (Відновити біт – це змінити біт з 0 на 1)

Giriş verilənləri

В першому рядку вводиться два числа: m ≤ 10^6 та k ≤ 10^6.

Çıxış verilənləri

В єдиному рядку потрібно вивести число n. Якщо варіантів декілька, потрібно вивести найменший можливий варіант. Якщо число зробити гарним неможливо, виведіть -1.

Nümunə

Giriş verilənləri #1
4 3
Çıxış verilənləri #1
6
Giriş verilənləri #2
39 6
Çıxış verilənləri #2
-1
Giriş verilənləri #3
9 3
Çıxış verilənləri #3
9

Qeyd

В першому прикладі m=4, тобто у двійковій системі числення воно записується як 100. Є три варіанти, які біти відновити:

• Відновити молодший біт. Тоді число стане 101[2] = 5[10] – не ділиться на 3.

• Відновити середній біт. Тоді число стане 110[2] = 6[10] – ділиться на 3.

• Відновити і молодший, і середній біти. Тоді число стане 111[2]=7[10] – не ділиться на 3.

Таким чином, єдиною відповіддю буде число 6.

Müəllif Жуковський Сергій Станіславович
Mənbə Джерело Серія задач "Абетка програмування"