出题人 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} \mathbin{\mathrm{xor}} \cdots \mathbin{\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 \mathbin{\mathrm{xor}} 1)+(4 \mathbin{\mathrm{xor}} 5 \mathbin{\mathrm{xor}} 1 \mathbin{\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\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载