T140977 线性基 (hard version)
题目背景
Ysu 是幼儿园的 OI 教练,今天 ta 打算教我们“最大异或和”这个题目:
> 给定 $n$ 个整数(数字可能重复),求在这些数中选取任意个,使得他们的异或和最大。
我们还是太年轻了。最开始我们想出了一种算法:
- **将数组 $a$ 从大到小排序**;
- 维护一个变量 $s$ 为临时答案;
- 下标 $i$ 从 $1\to n$ 遍历数组,对于每一个 $i$ 都执行 $s\gets \max\{s,s\oplus a_i\}$。
- 最后返回答案为 $s$。
但这个做法马上被 Ysu hack 了。
题目描述
Ysu 并不认为我们很菜,而是提出了一个令人深思的问题:假设对于“最大异或和”这个问题,正确答案是 $A$,我们的算法给出的答案是 $B$,能否构造一个长度为 $n$ 的数组使得 $A-B=k$?
你构造的数组元素必须为整数且 $\in[1,10^6]$。
输入格式
两个整数 $n,k$。
输出格式
如果不存在答案,输出 `-1`。
否则输出你构造的数组,两个数之间由空格隔开。如果有多解,输出一个即可。
说明/提示
### 样例说明
在第一个样例中,我们可以计算出 $A=7$,$B=6$,$A-B=1$。
在第二个样例中,我们可以计算出 $A=447$,$B=386$,$A-B=61$。
### 数据范围
对于 $100\%$ 的数据,$2\le n\le 10^5$,$0\le k \le 10^5$。