有一天,在一场艰难的讲座之后,一位勤奋的学生萨莎在教室里看到了一张涂鸦的桌子。她走近一看,读到:“找到这样的正整数 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