Khoảng cách Hamming

Time limit: 4.0 s
Memory limit: 1 GB
Points: 100partial
AC rate: 57.1%
Solvers: 3

Khoảng cách Hamming của hai số được định nghĩa là số lượng bit khác nhau trong biểu diễn nhị phân của hai số đó.

Cho số nguyên dương $m$ ~m~ và mảng $a$ ~a~ gồm $n$ ~n~ số nguyên $a_1,a_2,...,a_n$ ~a_1,a_2,...,a_n~ $(a_i \le 2^m)$ ~(a_i \le 2^m)~ Với mỗi phần tử $a_i$ ~a_i~, tìm khoảng cách Hamming lớn nhất giữa nó với các phần tử khác trong mảng.

Hay nói cách khác, với mỗi phần tử $a_i$ ~a_i~, yêu cầu tính:

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

Input

Dòng đầu tiên chứa hai số nguyên $n$ ~n~ và $m$ ~m~ $(1 \le n \le 2^m;\; 1 \le m \le 20)$ ~(1 \le n \le 2^m;\; 1 \le m \le 20)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên $a_i$ ~a_i~ $(0 \le a_i < 2^m)$ ~(0 \le a_i < 2^m)~.

Output

In ra trên một dòng gồm $n$ ~n~ số nguyên là khoảng cách Hamming lớn nhất với các phần tử khác của từng phần tử.

Samples

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

Scoring

Subtask $1$ ~1~ với $30\%$ ~30\%~ số điểm: $m \le 10$ ~m \le 10~
Subtask $2$ ~2~ với $30\%$ ~30\%~ số điểm: $m \le 16$ ~m \le 16~
Subtask $3$ ~3~ với $40\%$ ~40\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

Trong ví dụ thứ ba, các số $3,4,6,10$ ~3,4,6,10~ được biểu diễn dưới dạng nhị phân lần lượt là $0011,0100,0110,1010$ ~0011,0100,0110,1010~. Phần tử giá trị $3$ ~3~ và $4$ ~4~ có khoảng cách Hamming là $3$ ~3~, tương tự với phần tử giá trị $4$ ~4~ và $10$ ~10~. Phần tử giá trị $6$ ~6~ có khoảng cách Hamming lớn nhất bằng $2$ ~2~ so với các phần tử khác.

Comments

You need to sign in to write comments, reply and vote.