#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}$