Lost Bits#9579
Kostya has a fondness for all natural numbers, but he especially loves those he considers beautiful. A number is deemed beautiful if it is divisible by .
One day, Kostya encountered a beautiful natural number, , while shopping. He was so taken with it that he decided to purchase it as a gift for his mother. However, upon returning home, he discovered that some bits of the number had somehow been lost, turning it into an unbeautiful number, . Your task is to help Kostya restore some bits so that the number becomes beautiful again. (Restoring a bit involves changing a bit from 0 to 1.)
The first line contains two integers: m \le 10^6 and k \le 10^6.
Print the number on a single line. If there are multiple possibilities, print the smallest possible option. If it is impossible to make the number beautiful, print -1.
Example 1
Example 2
Example 3
Consider the first example where m=4, which is represented in binary as 100. There are three potential ways to restore the bits:
Restore the least significant bit, resulting in 101[2] = 5[10], which is not divisible by 3.
Restore the middle bit, resulting in 110[2] = 6[10], which is divisible by 3.
Restore both the least significant and middle bits, resulting in 111[2] = 7[10], which is not divisible by 3.
Therefore, the only valid solution is the number 6.