시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB174436.364%

## 문제

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: $$\max_{1 \le j \le n}hamming(a_i, a_j)$$

## 입력

The first line contains two integers $n$ and $m$ ($1 ≤ n ≤ 2^m$, $1 ≤ m ≤ 20$).

The second line contains $n$ numbers $a_i$ ($0 ≤ a_i < 2^m$)

## 출력

Output $n$ numbers seperated with spaces, where the $i$-th number is the maximum hamming distance between $a_i$ and some other number in $a$.

## 서브태스크

번호배점제한
120

$m ≤ 10$

225

$m ≤ 16$

325

## 예제 입력 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


## 힌트

Clarification of the third example: 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 with all other numbers.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.