Page not loading? Try clicking here.
Placeholder

#5686

해밍 경로 2 2s 1024MB

Problems

N개의 음이 아닌 2^M 미만의 정수들 A_1, A_2, \dots, A_N이 주어진다. 각각의 정수들에 대하여 다른 정수들과의 가능한 최대 해밍 경로를 찾아야한다.

해밍 경로는 음이 아닌 두 정수들에 대하여 이진수로 변환 시 같은 위치에 대해 다른 수들의 개수이다. (필요의 따라 앞에 붙는 0들도 포함된다)

수식으로 표현하자면 다음과 같다: \smash{\displaystyle\max_{i \le j \le N}} hamming(A_i, A_j)


Input

첫 번째 줄에 두 정수 N과 M이 입력된다 (1 \le N \le 2^M, 1 \le M \le 20).

두 번째 줄에 N개의 정수 A_i가 입력된다 (0 \le A_i \le 2^M).


Output

N개의 정수를 공백으로 나누어 출력하시오. 각 i번째 정수는 A_i의 다른 정수들 간의 최대 해밍 경로이다.


Subtask

# Score Condition
#120

M \le 10

#225

M \le 16

#355

제한 없음


Example #1

4 4
9 12 9 11
2 3 2 3

Example #2

4 4
5 7 3 9
2 3 2 3

Example #3

4 4
3 4 6 10
3 3 2 3

3, 4, 6, 10은 이진수로 0011, 0100, 0110, 1010으로 표현된다. 3과 4, 그리고 4와 10은 해밍 경로가 3이며, 6은 모든 다른 정수와 해밍 경로가 2이다.



Source

COCI 2022/2023 Contest #5 2번

You must sign in to write code.