CF1523D.Love-Hate

William is hosting a party for $n$ of his trader friends. They started a discussion on various currencies they trade, but there's an issue: not all of his trader friends like every currency. They like some currencies, but not others.

For each William's friend $i$ it is known whether he likes currency $j$. There are $m$ currencies in total. It is also known that a trader may not like more than $p$ currencies.

Because friends need to have some common topic for discussions they need to find the largest by cardinality (possibly empty) subset of currencies, such that there are at least $\lceil \frac{n}{2} \rceil$ friends (rounded up) who like each currency in this subset.

威廉正在为他的 $n$ 位交易员朋友举办一场聚会。朋友们开始讨论他们所交易的各种货币，但存在一个问题：并非所有朋友都喜欢每一种货币。他们只喜欢其中一部分货币，而对另一些则不感兴趣。

对于威廉的每位朋友 $i$，已知他是否喜欢货币 $j$。总共有 $m$ 种货币。此外还已知：每位交易员最多只喜欢 $p$ 种货币。

由于朋友们需要一个共同话题来展开讨论，因此他们需要找出一个基数最大（允许为空集）的货币子集，使得该子集中每一种货币都至少被 $\lceil \frac{n}{2} \rceil$ 位朋友（向上取整）所喜欢。

The first line contains three integers $n, m$ and $p$ $(1 \le n \le 2 \cdot 10^5, 1 \le p \le m \le 60, 1 \le p \le 15)$, which is the number of trader friends, the number of currencies, the maximum number of currencies each friend can like.

Each of the next $n$ lines contain $m$ characters. The $j$-th character of $i$-th line is $1$ if friend $i$ likes the currency $j$ and $0$ otherwise. It is guaranteed that the number of ones in each line does not exceed $p$.

第一行包含三个整数 $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$ 个字符。第 $i$ 行的第 $j$ 个字符为 $1$ 表示第 $i$ 位朋友喜欢第 $j$ 种货币，为 $0$ 则表示不喜欢。保证每行中字符 $1$ 的个数不超过 $p$。

Print a string of length $m$, which defines the subset of currencies of the maximum size, which are liked by at least half of all friends. Currencies belonging to this subset must be signified by the character $1$.

If there are multiple answers, print any.

输出一个长度为 $m$ 的字符串，该字符串表示一个最大规模的货币子集，该子集中的每种货币至少被一半的朋友喜欢。属于该子集的货币需用字符 $1$ 表示。

若存在多个答案，输出任意一个即可。

In the first sample test case only the first currency is liked by at least $\lceil \frac{3}{2} \rceil = 2$ friends, therefore it's easy to demonstrate that a better answer cannot be found.

In the second sample test case the answer includes $2$ currencies and will be liked by friends $1$, $2$, and $5$. For this test case there are other currencies that are liked by at least half of the friends, but using them we cannot achieve a larger subset size.

在第一个样例测试用例中，只有第一种货币被至少 $\lceil \frac{3}{2} \rceil = 2$ 位朋友喜欢，因此容易证明无法找到更优的答案。

在第二个样例测试用例中，答案包含 $2$ 种货币，且将被朋友 $1$、$2$ 和 $5$ 喜欢。对于该测试用例，存在其他被至少一半朋友喜欢的货币，但使用它们无法获得更大的子集规模。