diskurs — COCI CONTEST_#5
Task type: batch | Time limit: 2 s | Memory limit: 512 MB | Difficulty: 16
Algorithms: data structures, greedy, bitmask, trie

![](_page_0_Picture_0.jpeg)

# Task Diskurs

You are given $n$ non-negative integers $a_1, a_2, ..., 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} \text{hamming}(a_i, a_j)
$$

## Input

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

The second line contains $n$ numbers $a_i$ ($0 \le a_i < 2^m$).

## Output

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

### Scoring

| Subtask | Points | Constraints                |
|---------|--------|----------------------------|
| 1       | 20     | $m \le 10$                 |
| 2       | 25     | $m \le 16$                 |
| 3       | 25     | No additional constraints. |

### Examples

| Input          | Input          | Input           |
|----------------|----------------|-----------------|
| 4 4            | 4 4            | 4 4            |
| 9 12 9 11      | 5 7 3 9        | 3 4 6 10        |
| Output         | Output         | Output          |
| 2 3 2 3          | 2 3 2 3        | 3 3 2 3         |

### Clarification of the third example:

The numbers 3, 4, 6, and 10 can be represented as 0011, 0100, 0110, and 1010 in binary. Numbers 3 and 4 differ at 3 places, as do numbers 4 and 10. On the other hand, the number 6 differs in at most 2 places with all other numbers.

Starter code: