Однажды после сложной лекции старательная студентка Саша увидела исписанную парту в аудитории. Присмотревшись, она прочитала следующее: «Найдите такое целое положительное n, что среди чисел n + 1, n + 2, ..., 2·n есть ровно m чисел, в двоичной записи которых ровно k единиц.»
Ее заинтересовало это задание, и она просит вас помочь ей его решить. Саша знает, что вы боитесь больших чисел, поэтому она гарантирует, что существует ответ не превышающий 1018.
Выходные данные
Выведите искомое число n (1 ≤ n ≤ 1018). Если ответов несколько — выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
|
1
|
|
2
|
3 2
|
5
|