给定 $n$ 个小于 $2^m$ 的非负整数 $a_1, a_2, \dots, a_n$。对于其中每一个数，你需要求出它与数组 $a$ 中其他元素之间可能的最大汉明距离（Hamming distance）。
两个非负整数的汉明距离定义为它们二进制表示中对应位不同的位置数量（必要时补前导零）。
形式化地，对于每个 $i$，计算： $$\max_{1 \le j \le n} \text{hamming}(a_i, a_j)$$
输入格式
第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 2^m, 1 \le m \le 20$)。
第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i < 2^m$)。
输出格式
输出 $n$ 个用空格分隔的数字，其中第 $i$ 个数字表示 $a_i$ 与数组 $a$ 中其他数字之间的最大汉明距离。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 20 | $m \le 10$ |
| 2 | 25 | $m \le 16$ |
| 3 | 25 | 无附加限制 |
样例
样例输入 1
4 4 9 12 9 11
样例输出 1
2 3 2 3
样例输入 2
4 4 5 7 3 9
样例输出 2
2 3 2 3
样例输入 3
4 4 3 4 6 10
样例输出 3
3 3 2 3
说明
第三个样例的解释： 数字 3, 4, 6, 10 的二进制表示分别为 0011, 0100, 0110, 1010。数字 3 和 4 在 3 个位置上不同，数字 4 和 10 也是如此。另一方面，数字 6 与其他所有数字相比，最多只有 2 个位置不同。