题目描述

Brabo 有 $n$ 张图片和一个图像处理 APP。对于任意 $1\leq i\leq n$，第 $i$ 张图片有一个对比度值 $v_i$。为了改善图片质量，该 APP 一次性接收一批图片（至少包含 $k$ 张图片），且这些图片之间的对比度应尽可能接近。

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

记 $c_i$ 为将前 $i$ 张图片划分成组时，所得到的最小的组内最大对比度差值。你的任务是计算这些值：$c_1, c_2, \cdots, c_n$。注意，当无法对前 $i$ 张图片进行划分时，$c_i$ 视为 $0$。

输入格式

第一行包含两个整数 $n$ $(1 \le n \le 1000000)$ 和 $k$ $(1 \le k \le n)$ —— 图片的数量，以及每组图片至少应包含的图片数。

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

输出格式

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

5 2
50 110 190 120 34

0
60
80
90
80

提示

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

翻译由 DeepSeek V4 Pro 完成