给定一个数组 $$$a$$$,由 $$$n$$$ 不同元素和一个整数 $$$k$$$ 组成。数组中的每个元素都是一个不超过$$$2^k-1$$$的非负整数。
让我们将数字 $$$x$$$ 的 XOR 距离定义为
$$$$$$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)$$$。
输入
第一行包含两个整数 $$$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$$$)。所有这些整数都是不同的。
输出
打印 $$$2^k$$$ 整数。其中第 $$$i$$$ 应等于 $$$f(i-1)$$$。
示例
输入 #1
3 3 6 0 3
输出 #1
3 1 1 2 2 1 1 3
输入 #2
3 4 13 4 2
输出 #2
2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2
注意
考虑第一个例子:
- 对于$$$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$$$。