← 返回题目列表

Codeforces · 431/D

D. 随机任务

中文机器翻译题面 查看原题

有一天,在一场艰难的讲座之后,一位勤奋的学生萨莎在教室里看到了一张涂鸦的桌子。她走近一看,读到:“找到这样的正整数 n,在数字 n + 1, n + 2, ..., 2·n 中,正好有 m 个数字,其二进制表示恰好包含 k 个数字 1”。

女孩对这个任务很感兴趣,她要求你帮她解决这个问题。 Sasha知道你害怕大数字,所以她保证有一个不超过1018的答案。

输入

第一行包含两个空格分隔的整数 m 和 k (0 ≤ m ≤ 1018; 1 ≤ k ≤ 64)。

输出

打印所需的数字 n (1 ≤ n ≤ 1018)。如果有多个答案,请打印其中任何一个。

示例

输入 #1

1 1

输出 #1

1

输入 #2

3 2

输出 #2

5