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)$$$.
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.
Print $$$2^k$$$ integers. The $$$i$$$-th of them should be equal to $$$f(i-1)$$$.
3 3 6 0 3
3 1 1 2 2 1 1 3
3 4 13 4 2
2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2
Consider the first example:
Name |
---|