#P1051. 新年的神签
新年的神签
新年有 $n$ 个吉祥数字 $d_1,\dots,d_n$,初始都为 $0$,楽马想把它们分别变成 $c_1,\dots,c_n$。
他可以填若干张神签,在一张神签上填 $x$ 会让每个吉祥数字 $d_i$ 异或上 $(a_i+x) \bmod 2^k$。
由于神签使用 $k$ 位二进制数存储,填写的数字必须是小于 $2^k$ 的非负整数。并且为了不浪费神签,楽马最多使用 $10^5$ 张。
请你帮楽马找到一个填神签的方案,或者输出 $-1$ 报告无解。
输入格式
第一行两个整数 $n,k$。
第二行 $n$ 个整数 $a_1,\dots,a_n$。
第三行 $n$ 个整数 $c_1,\dots,c_n$。
输出格式
无解输出一行一个整数 $-1$。
否则第一行输出一个整数 $m$,即填的神签数量。第二行输出 $m$ 个整数 $b_1,\dots,b_m$,即每张神签填的数字。
5 4
2 1 4 3 5
4 4 12 12 12
2
1 5
3 3
1 2 3
3 2 1
-1
样例三 $\sim$ 九
见“附件下载”。
数据范围
$1\leq n,k\leq 50$,$0\leq a_i,c_i<2^k$。
| 子任务编号 | $n\leq$ | $k\leq$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $10$ | $4$ | 无 | $8$ |
| $2$ | $20$ | $10$ | 无 | $15$ |
| $3$ | $20$ | $50$ | $a_i<2^{10}$ | $17$ |
| $4$ | $2$ | $50$ | 无 | $12$ |
| $5$ | $50$ | $50$ | A | $15$ |
| $6$ | $20$ | $30$ | 无 | $16$ |
| $7$ | $50$ | $50$ | 无 | $17$ |
特殊性质 A:保证数据生成方式为,先固定 $n,k$ 和 $m=10^4$,再在 $[0,2^k)$ 中均匀随机 $a_i,b_j$,并求出对应的 $c_i$。
时间限制:$2\texttt{s}$
空间限制:$1\texttt{GB}$