Bit sorting#1649
We define the following order on the set of non-negative integers: For two numbers and , we say that is less than if one of the following holds:
The number of ones in the binary representation of is less than that of .
The number of ones in the binary representation of equals that of , and A < B (in the usual sense).
Now, sort all integers from to inclusive in ascending order according to this new relation. Your task is to determine which number will be at position . Positions are numbered starting from one.
The first line contains two integers and (0 \leq n \leq 10^{16}, 1 \leq k \leq n + 1).
Print the -th number in the sorted sequence.
Example 1
The numbers from to will be sorted as follows: , , , , , , , , , , .