Brabo 拥有 $n$ 张图像和一个图像处理 APP。对于任意 $1 \le i \le n$，第 $i$ 张图像都有一个对比度值 $v_i$。为了优化图像效果，APP 会接收一批图像（包含至少 $k$ 张图像），且这些图像之间的对比度应尽可能接近。

Brabo 已经知道了所有这些图像的对比度值 $v_i$，现在他需要确定一种分组方案，将图像划分为若干组，使得每组至少包含 $k$ 张图像，且每张图像都属于某一个组。此外，同一组内图像对比度值的最大差值应尽可能小。注意，Brabo 不能重新排列这些图像的顺序。也就是说，每一组必须包含若干索引连续的图像。

令 $c_i$ 表示将前 $i$ 张图像划分为若干组时，各组内最大对比度差值的最小值。你的任务是计算这些值：$c_1, c_2, \dots, c_n$。注意，当无法将前 $i$ 张图像进行合法分组时，$c_i$ 记为 $0$。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 1000000$) 和 $k$ ($1 \le k \le n$)，分别表示图像的数量，以及每组图像应包含的最小数量。

下一行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 2 \times 10^9$)，表示这些图像加密后的对比度 $v_i$。实际的 $v_i$ 为 $x_i \oplus c_{i-1}$，其中 $\oplus$ 表示按位异或运算。注意 $c_0 = 0$。保证解密后的 $1 \le v_i \le 10^9$。

输出格式

输出 $n$ 行，其中第 $i$ ($1 \le i \le n$) 行包含一个整数，即最小对比度差值 $c_i$。

样例

输入 1

5 2
50 110 190 120 34

输出 1

0
60
80
90
80

说明

在样例测试中，$v = [50, 110, 130, 40, 120]$。