К Василию в гости пришло $$$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$$$. В этом тесте есть и другие валюты, которые нравятся хотя бы половине друзей, но с их помощью нельзя добиться большего размера множества.
