Jamie 正在准备 Codeforces 回合。他对一个问题有了一个想法,但不知道如何解决。帮助他写出以下问题的解决方案:
找到 k 个整数,使每个数字的 2 次方之和等于数字 n,并且答案中最大的整数尽可能小。由于可能有多个答案,因此要求您输出字典顺序最大的一个。
为了更清楚,请考虑长度为 k (a1, a2, ..., ak) 且 $$\sum_{i=1}^{k} 2^{a_i} = n$$ 的所有整数序列。为每个序列指定一个值 $$y = \max_{1 \leq i \leq k} a_i$$ 。在具有最小 y 值的所有序列中,输出字典顺序最大的序列。
有关权力的定义和字典顺序,请参阅注释。
输入
第一行由两个整数 n 和 k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 105) 组成 - 所需的总和以及序列的长度。
输出
如果不存在这样的序列,则在单行中输出“No”(不带引号)。否则,在第一行中输出“Yes”(不带引号),并在第二行中输出用空格分隔的 k 个数字 - 所需的序列。
保证答案序列中的整数符合范围 [ - 1018, 1018]。
示例
输入 #1
23 5
输出 #1
Yes 3 3 2 1 0
输入 #2
13 2
输出 #2
No
输入 #3
1 2
输出 #3
Yes -1 -1
注意
示例 1:
23 + 23 + 22 + 21 + 20 = 8 + 8 + 4 + 2 + 1 = 23
像 (3, 3, 2, 0, 1) 或 (0, 1, 2, 3, 3) 这样的答案并不是字典顺序最大的。
像 (4, 1, 1, 1, 0) 这样的答案没有最小 y 值。
示例 2:
可以证明不存在长度为2的序列。
示例 3:
$$2^{-1} + 2^{-1} = \frac{1}{2} + \frac{1}{2} = 1$$
2 的幂:
如果 x > 0,则 2x = 2·2·2·...·2(x 次)。
如果 x = 0,则 2x = 1。
如果 x < 0,则 $$2^x = \frac{1}{2^{-x}}$$。
字典顺序:
给定两个相同长度的不同序列 (a1, a2, ... , ak) 和 (b1, b2, ... , bk),对于字典顺序,第一个序列小于第二个序列,当且仅当 ai < bi,对于第一个 i,其中 ai 和 bi 不同。