Problem Description

You are given $n$ non-negative integers $a_1, a_2, \cdots, a_n$, each of which is less than $2^m$.

For each number, you need to find the maximum Hamming distance between it and any other element in the array.

The Hamming distance between two non-negative integers is defined as the number of differing positions in their binary representations (with leading zeros added if necessary).

Formally, for each $i$, find:

$$\max\limits_{1\leq j\leq n} hamming(a_i,a_j)$$

Input Format

The first line contains two integers $n$ and $m$ $(1 \leq n \leq 2^m, 1 \leq m \leq 20)$.
The second line contains $n$ numbers $a_i$ $(0 \leq a_i < 2^m)$.

Output Format

A single line containing $n$ numbers, where the $i$-th number represents the maximum Hamming distance between $a_i$ and any other element in the array.

Sample Input and Output

Input Sample #1

4 4
9 12 9 11

Output Sample #1

2 3 2 3

Input Sample #2

4 4
5 7 3 9

Output Sample #2

2 3 2 3

Input Sample #3

4 4
3 4 6 10

Output Sample #3

3 3 2 3

Notes/Hints

见题面 Input 部分

见题面 Output 部分