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 \underset{1\le j\le n}{max}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.