【cf437B】The Child and Set

2014年6月3日1,1420

At the children’s day, the child came to Picks’s house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite set of Picks.

Fortunately, Picks remembers something about his set S:

  • its elements were distinct integers from 1 to limit;
  • the value of  was equal to sum; here lowbit(x) equals 2k where k is the position of the first one in the binary representation of x. For example, lowbit(100102) = 102, lowbit(100012) = 12, lowbit(100002) = 100002 (binary representation).

Can you help Picks and find any set S, that satisfies all the above conditions?

Input

The first line contains two integers: sum, limit (1 ≤ sum, limit ≤ 105).

Output

In the first line print an integer n (1 ≤ n ≤ 105), denoting the size of S. Then print the elements of set S in any order. If there are multiple answers, print any of them.

If it’s impossible to find a suitable set, print -1.

Sample test(s)
input

output

input

output

input

output

Note

In sample test 1: lowbit(4) = 4, lowbit(5) = 1, 4 + 1 = 5.

In sample test 2: lowbit(1) = 1, lowbit(2) = 2, lowbit(3) = 1, 1 + 2 + 1 = 4.

题意 orz wyl8899

在儿童节这一天,我们的小朋友来到了Picks的家,把他家里弄得一团糟。Picks非常生气。很多重要的东西都不见了,这其中包括了Picks最喜欢的集合。
幸运的是,Picks记得一些关于他的集合S的事情:
1. 其元素是1至limit间的互异整数;
2. 所有lowbit(x)之和(x取遍S中的所有元素)等于sum,这里lowbit(x)等于2^k,k是x的二进制表示中第一个1的位置。例如(以下数字均为二进制表示),lowbit(10010)=10,lowbit(10001)=1,lowbit(10000)=10000。
你能帮助Picks找到一个符合上述条件的集合S吗?
Input
一行,两个整数,依次是sum和limit(1<=sum,limit<=10^5)。
Output
第一行输出n(1<=n<=10^5),为集合S的大小。然后在下一行以任意顺序输出S的所有元素。如果有多个符合要求的集合,输出任意一个即可。
如果找不到这样的集合,输出-1。

题解

首先可以得出1到limit每一个数对于答案的贡献

然后从大往小取就行了