410431: GYM104021 C Image Processing

Brabo has $$$n$$$ images and an image processing APP. The $$$i$$$-th image, for any $$$1\leq i\leq n$$$, has a contrast value $$$v_i$$$. To make the images better, the APP receives a batch of images together (which contains at least $$$k$$$ images) and the contrast between these images should be as close as possible.

Brabo has already known the contrast values $$$v_i$$$ of all these images, and now he has to determine a partition splitting images into groups so that each group has at least $$$k$$$ images, and each image should belong to a certain group. Moreover, the maximal difference of contrast values for images in the same group should be as small as possible. Note that Brabo cannot rearrange the order of these images. That is, each group must contain several images with continuous indexes.

Let's denote $$$c_i$$$ as the smallest maximal difference of contrast values for splitting the first $$$i$$$ images into groups. Your task is to compute these values: $$$c_1, c_2, \cdots, c_n$$$. Note that when it is impossible to partition the first $$$i$$$ images, $$$c_i$$$ is regarded as $$$0$$$.

The first line contains two integers $$$n~(1 \le n \le 1000000)$$$ and $$$k~(1 \le k \le n)$$$ — the number of images, and each group of images should contain no less than $$$k$$$ images.

The next line contains $$$n$$$ integers $$$x_1, x_2, \cdots, x_n~(0 \le x_i \le 2\times 10^9)$$$ — the encrypted contrast $$$v_i$$$ of these images. The actual $$$v_i$$$ is $$$x_i\oplus c_{i-1}$$$, where $$$\oplus$$$ denotes bitwise exclusive-or. Note that $$$c_0=0$$$. It is guaranteed that $$$1\leq v_i\leq 10^9$$$ after decryption.

Output $$$n$$$ lines, where the $$$i$$$-th $$$(1\le i \le n)$$$ line contains a single integer, the smallest contrast differences $$$c_i$$$.

5 2
50 110 190 120 34

0
60
80
90
80

In the sample test, $$$v=[50,110,130,40,120]$$$.