К Василию в гости пришло \(n\) друзей-трейдеров. Они начали обсуждать разные валюты, которыми торговали, но вот незадача: далеко не всем его друзьям нравится каждая валюта, некоторые валюты они любят, а некоторые — нет.
Для каждого друга Василия \(i\) известно, нравится ли ему валюта \(j\). Всего валют \(m\). Известно, что трейдерам не может нравится больше, чем \(p\) валют.
Так как друзьям нужно найти что-то общее для обсуждения, им нужно найти максимальное по мощности (возможно пустое) подмножество валют такое, что найдется как минимум \(\lceil \frac{n}{2} \rceil\) друзей (округление в большую сторону), каждому из которых будут нравиться все валюты этого множества.
Выходные данные
Выведите строку длины \(m\), задающую максимальное по размеру подмножество валют, которые нравятся хотя бы половине друзей. Символом \(1\) должны быть обозначены валюты, которые принадлежат этому подмножеству.
Если ответов несколько, то вы можете вывести любой подходящий.
Примечание
В первом тестовом примере только первая валюта нравится как минимум \(\lceil \frac{3}{2} \rceil = 2\) друзьям, поэтому легко показать, что ответ лучше составить нельзя.
Во втором тестовом примере максимальный ответ содержит \(2\) валюты и будет нравится друзьям под номерами \(1\), \(2\) и \(5\). В этом тесте есть и другие валюты, которые нравятся хотя бы половине друзей, но с их помощью нельзя добиться большего размера множества.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 3
1000
0110
1001
|
1000
|
|
2
|
5 5 4
11001
10101
10010
01110
11011
|
10001
|