出题人 01 很喜欢加法，也很喜欢异或运算（即 C/C++ 里的 ^ 运算符）。有天他一拍脑袋：把两个运算混一起，岂不是妙极了？

对于一个序列 $b_1,\dots ,b_m$，他希望你将序列 $b$ 划分为 $k$ 段连续非空子序列，使得每一段的异或和之和最小。即，他想知道在所有满足 $0=p_0<p_1<\cdots <p_k=m$ 条件的序列 $p$ 中下式的最小值： $$\sum _{i=1}^k(b_{p_{i-1}+1}\mathrm{xor}\cdots \mathrm{xor}{b}_{p_i})$$ 这个最小值即称为这个序列的妙妙值。

但是这个问题非常简单，于是出题人 01 找来了一个长度恰好为 $n$ 的非负整数序列 $a_1,\dots ,a_n$。他想考考你，$a$ 的每个前缀 $a_1,\dots ,a_j$ （$k\le j\le n$）的妙妙值分别是多少呢？

输入格式

第一行两个正整数 $n,k$，含义同题面。

接下来一行 $n$ 个非负整数，第 $i$ 个非负整数表示 $a_i$。

输出格式

第一行 $n-k+1$ 个整数，分别表示前 $j=k,k+1,\dots ,n$ 个元素组成的序列的妙妙值。

样例一

input

6 2
1 1 4 5 1 4

output

2 4 1 0 4

explanation

对于序列 $a_1,\dots ,a_6$,可以将序列划分为 $a_1,a_2$ 和 $a_3,a_4,a_5,a_6$ 两段。

此时答案为 $(1\mathrm{xor}1)+(4\mathrm{xor}5\mathrm{xor}1\mathrm{xor}4)=0+4=4$。

注意 $a_1,a_2,a_3,a_4,a_5$ 和 $a_6$ 也是一种合法的划分方案。

样例二

见下发文件。

数据范围同测试点 3 ~ 4。

限制与约定

对于所有测试点，满足 $1\le k\le n\le 60000,k\le 8,a_i<2^{16}$

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载