You are given ~n~ non-negative integers ~a_1, a_2, \dots, a_n~ less than ~2^m~. For each of them, you are to find the maximum possible Hamming distance between it and some other element of the array ~a~.

The Hamming distance of two non-negative integers is defined as the number of positions in the binary representation of these numbers in which they differ (we add leading zeros if necessary).

Formally, for each ~i~, calculate:

$$\displaystyle \max_{1 \le j \le n} hamming(a_i, a_j)$$

Input Specification

The first line contains two integers, ~n~ and ~m~ ~(1 \le n \le 2^m, 1 \le m \le 20)~.

The second line contains ~n~ integers, ~a_i~ ~(0 \le a_i < 2^m)~.

Output Specification

Output ~n~ integers separated with spaces, where the ~i~-th integer is the maximum Hamming distance between ~a_i~ and some other number in ~a~.

Constraints

Subtask	Points	Constraints
1	20	~m \le 10~
2	25	~m \le 16~
3	25	No additional constraints.

Sample Input 1

4 4
9 12 9 11

Sample Output 1

2 3 2 3

Sample Input 2

4 4
5 7 3 9

Sample Output 2

2 3 2 3

Sample Input 3

4 4
3 4 6 10

Sample Output 3

3 3 2 3

Explanation for Sample 3

The numbers ~3, 4, 6, 10~ can be represented as ~0011, 0100, 0110, 1010~ in binary. Numbers ~3~ and ~4~ differ at ~3~ places, same as numbers ~4~ and ~10~. On the other hand, the number ~6~ differs in at most ~2~ places from all other numbers.