CF1553H.XOR and Distance

You are given an array $a$ consisting of $n$ distinct elements and an integer $k$. Each element in the array is a non-negative integer not exceeding $2^k-1$.

Let's define the XOR distance for a number $x$ as the value of

$$f(x) = \\min\\limits\_{i = 1}^{n} \\min\\limits\_{j = i + 1}^{n} |(a\_i \\oplus x) - (a\_j \\oplus x)|,$$

where $\oplus$ denotes the bitwise XOR operation.

For every integer $x$ from $0$ to $2^k-1$, you have to calculate $f(x)$.

给你一个由 $n$ 个互不相同元素组成的数组 $a$ 和一个整数 $k$。数组中每个元素均为不超过 $2^k-1$ 的非负整数。

我们定义一个数 $x$ 的异或距离为如下值：

$$f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,$$

其中 $\oplus$ 表示按位异或运算。

你需要对每个从 $0$ 到 $2^k-1$ 的整数 $x$，计算出 $f(x)$。

The first line contains two integers $n$ and $k$ ($1 \le k \le 19$; $2 \le n \le 2^k$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2^k-1$). All these integers are distinct.

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le 19$；$2 \le n \le 2^k$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 2^k-1$）。这些整数互不相同。

Print $2^k$ integers. The $i$-th of them should be equal to $f(i-1)$.

输出 $2^k$ 个整数。其中第 $i$ 个整数应等于 $f(i-1)$。

Consider the first example:

• for $x = 0$, if we apply bitwise XOR to the elements of the array with $x$, we get the array $[6, 0, 3]$, and the minimum absolute difference of two elements is $3$;
• for $x = 1$, if we apply bitwise XOR to the elements of the array with $x$, we get the array $[7, 1, 2]$, and the minimum absolute difference of two elements is $1$;
• for $x = 2$, if we apply bitwise XOR to the elements of the array with $x$, we get the array $[4, 2, 1]$, and the minimum absolute difference of two elements is $1$;
• for $x = 3$, if we apply bitwise XOR to the elements of the array with $x$, we get the array $[5, 3, 0]$, and the minimum absolute difference of two elements is $2$;
• for $x = 4$, if we apply bitwise XOR to the elements of the array with $x$, we get the array $[2, 4, 7]$, and the minimum absolute difference of two elements is $2$;
• for $x = 5$, if we apply bitwise XOR to the elements of the array with $x$, we get the array $[3, 5, 6]$, and the minimum absolute difference of two elements is $1$;
• for $x = 6$, if we apply bitwise XOR to the elements of the array with $x$, we get the array $[0, 6, 5]$, and the minimum absolute difference of two elements is $1$;
• for $x = 7$, if we apply bitwise XOR to the elements of the array with $x$, we get the array $[1, 7, 4]$, and the minimum absolute difference of two elements is $3$.

考虑第一个例子：

• 当 $x = 0$ 时，将数组中各元素与 $x$ 进行按位异或运算，得到数组 $[6, 0, 3]$，其中任意两元素的最小绝对差值为 $3$；
• 当 $x = 1$ 时，将数组中各元素与 $x$ 进行按位异或运算，得到数组 $[7, 1, 2]$，其中任意两元素的最小绝对差值为 $1$；
• 当 $x = 2$ 时，将数组中各元素与 $x$ 进行按位异或运算，得到数组 $[4, 2, 1]$，其中任意两元素的最小绝对差值为 $1$；
• 当 $x = 3$ 时，将数组中各元素与 $x$ 进行按位异或运算，得到数组 $[5, 3, 0]$，其中任意两元素的最小绝对差值为 $2$；
• 当 $x = 4$ 时，将数组中各元素与 $x$ 进行按位异或运算，得到数组 $[2, 4, 7]$，其中任意两元素的最小绝对差值为 $2$；
• 当 $x = 5$ 时，将数组中各元素与 $x$ 进行按位异或运算，得到数组 $[3, 5, 6]$，其中任意两元素的最小绝对差值为 $1$；
• 当 $x = 6$ 时，将数组中各元素与 $x$ 进行按位异或运算，得到数组 $[0, 6, 5]$，其中任意两元素的最小绝对差值为 $1$；
• 当 $x = 7$ 时，将数组中各元素与 $x$ 进行按位异或运算，得到数组 $[1, 7, 4]$，其中任意两元素的最小绝对差值为 $3$。