D. Нравится - не нравится
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

К Василию в гости пришло $$$n$$$ друзей-трейдеров. Они начали обсуждать разные валюты, которыми торговали, но вот незадача: далеко не всем его друзьям нравится каждая валюта, некоторые валюты они любят, а некоторые — нет.

Для каждого друга Василия $$$i$$$ известно, нравится ли ему валюта $$$j$$$. Всего валют $$$m$$$. Известно, что трейдерам не может нравится больше, чем $$$p$$$ валют.

Так как друзьям нужно найти что-то общее для обсуждения, им нужно найти максимальное по мощности (возможно пустое) подмножество валют такое, что найдется как минимум $$$\lceil \frac{n}{2} \rceil$$$ друзей (округление в большую сторону), каждому из которых будут нравиться все валюты этого множества.

Входные данные

В первой строке заданы три числа $$$n, m$$$ и $$$p$$$ $$$(1 \le n \le 2 \cdot 10^5, 1 \le p \le m \le 60, 1 \le p \le 15)$$$ — количество друзей-трейдеров, количество валют и максимальное количество валют, которые нравятся каждому другу.

Далее следует $$$n$$$ строк по $$$m$$$ символов в каждой. $$$j$$$-й символ в $$$i$$$-й строке равен $$$1$$$, если другу $$$i$$$ нравится валюта $$$j$$$, и $$$0$$$ — если не нравится. Гарантируется, что количество единиц в каждой строке не превышает $$$p$$$.

Выходные данные

Выведите строку длины $$$m$$$, задающую максимальное по размеру подмножество валют, которые нравятся хотя бы половине друзей. Символом $$$1$$$ должны быть обозначены валюты, которые принадлежат этому подмножеству.

Если ответов несколько, то вы можете вывести любой подходящий.

Примеры
Входные данные
3 4 3
1000
0110
1001
Выходные данные
1000
Входные данные
5 5 4
11001
10101
10010
01110
11011
Выходные данные
10001
Примечание

В первом тестовом примере только первая валюта нравится как минимум $$$\lceil \frac{3}{2} \rceil = 2$$$ друзьям, поэтому легко показать, что ответ лучше составить нельзя.

Во втором тестовом примере максимальный ответ содержит $$$2$$$ валюты и будет нравится друзьям под номерами $$$1$$$, $$$2$$$ и $$$5$$$. В этом тесте есть и другие валюты, которые нравятся хотя бы половине друзей, но с их помощью нельзя добиться большего размера множества.