409583: GYM103637 K K-ones xor

You are given integers $$$n, m$$$ and an array $$$a_1, a_2, ... , a_n$$$ of length $$$n$$$ consisting of $$$m$$$-bit integers. You are also given an integer $$$k$$$. You need to find $$$m$$$-bit integer $$$x$$$, which has no more than $$$k$$$ ones in binary representation. Out of all this numbers, you need to find such number, that after applying $$$a_i = max(a_i, a_i \oplus x)$$$ to the array, sum of the array will be maximal. $$$\oplus$$$ denotes the operation of bitwise $$$XOR$$$. If there are multiple such numbers, you need to find the minimal one.

The first line of input file contains three integers $$$n, m, k$$$. The second line of input file contains the array $$$a_1, a_2, ... , a_n$$$.

$$$$$$1 \le n \le 10^5$$$$$$ $$$$$$1 \le m \le 30$$$$$$ $$$$$$0 \le k \le m$$$$$$ $$$$$$0 \le a_i < 2^m$$$$$$

Output single number $$$x$$$ - answer for the task. $$$$$$0 \le x < 2^m$$$$$$

3 2 2
3 2 2

1

2 1 1
0 0

1