Diskurs

Σας δίνονται ~n~ μη αρνητικοί ακέραιοι ~a_1~, ~a_2~, ... , ~a_n~ μικρότεροι από το ~2^m~. Για κάθε έναν από αυτούς πρέπει να βρείτε την μέγιστη δυνατή απόσταση hamming μεταξύ του παραπάνω αριθμού και κάποιου άλλου στοιχείου του πίνακα ~a~.

Η απόσταση hamming δύο μη αρνητικών ακέραιων ορίζεται ως ο αριθμός των θέσεων στη δυαδική αναπαράσταση αυτών των αριθμών στις οποίες διαφέρουν (προσθέτουμε μηδενικά στην αρχή του αριθμού αν είναι απαραίτητο).

Επίσημα, για κάθε ~i~ υπολογίστε: max hamming(~a_i~, ~a_j~), όπου ~1~ ~\le~ ~j~ ~\le~ ~n~

Είσοδος

Η πρώτη γραμή περιέχει δύο ακέραιους ~n~ και ~m~ (~1~ ~\le~ ~n~ ~\le~ ~2^m~, ~1~ ~\le~ ~m~ ~\le~ ~20~)

Η δεύτερη γραμμή περιέχει ~n~ αριθμούς ~a_i~ (~0~ ~\le~ a_i~ ~\lt~ ~2^m~).

Έξοδος

Εκτυπώστε ~n~ αριθμούς χωρισμένους με κενά, όπου ο ~i~-οστος αριθμός είναι η μέγιστη απόσταση hamming μεταξύ του ~a_i~ και κάποιον άλλον αριθμό στο ~a~

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~m~ ~\le~ ~10~
2	25	~m~ ~\le~ ~16~
3	25	Κανένας επιπλέον περιορισμός

Παραδείγματα

input

4 4
9 12 9 11

output

2 3 2 3

input

4 4
5 7 3 9

output

2 3 2 3

input

4 4
3 4 6 10

output

3 3 2 3

Επεξήγηση του 3ου παραδείγματος:

Οι αριθμοί ~3~,~4~,~6~,~10~ μπορούν να αναπαρασταθούν ως ~0011~, ~0100~, ~0110~, ~1010~, στο δυαδικό σύστημα. Οι αριθμοί ~3~ και ~4~ διαφέρουν σε ~3~ σημεία, το ίδιο με τους αριθμούς ~4~ και ~10~. Από την άλλη, ο αριθμός ~6~ διαφέρει το πολύ σε ~2~ σημεία με όλους τους άλλους αριθμούς.