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