Загублені біти#9579
Костя полюбляє всі натуральні числа, але гарні числа – його найулюбленіші. Гарними числами він вважає числа, які націло діляться на .
Одного разу Костя побачив в крамниці гарне натуральне число . Йому воно так сподобалося, що він вирішив його купити та подарувати своїй мамі. Але коли Костя прийшов додому він побачив, що десь загубив деякі біти цього числа і воно стало негарним числом . Допоможіть йому відновити деякі біти, щоб число знову стало гарним. (Відновити біт – це змінити біт з 0 на 1)
В першому рядку вводиться два числа: m \le 10^6 та k \le 10^6.
В єдиному рядку потрібно вивести число . Якщо варіантів декілька, потрібно вивести найменший можливий варіант. Якщо число зробити гарним неможливо, виведіть -1.
Приклад 1
Приклад 2
Приклад 3
В першому прикладі m=4, тобто у двійковій системі числення воно записується як 100. Є три варіанти, які біти відновити:
• Відновити молодший біт. Тоді число стане 101[2] = 5[10] – не ділиться на 3.
• Відновити середній біт. Тоді число стане 110[2] = 6[10] – ділиться на 3.
• Відновити і молодший, і середній біти. Тоді число стане 111[2]=7[10] – не ділиться на 3.
Таким чином, єдиною відповіддю буде число 6.