Problem D
Distinctive Character
The similarity between two characters $A$ and $B$ is calculated as follows: for each feature $f$, if both $A$ and $B$ have feature $f$ or if none of them have feature $f$, the similarity increases by one.
Tira does not have a character yet. She would like to create a new, very original character so that the maximum similarity between Tira’s character and any other character is as low as possible.
Given the characters of the other players, your task is to create a character for Tira that fulfils the above requirement. If there are many possible characters, you can choose any of them.
Input
The first line of input contains two integers $n$ and $k$, where $1 \le n \le 10^5$ is the number of players (excluding Tira) and $1 \le k \le 20$ is the number of features.
Then follow $n$ lines describing the existing characters. Each of these $n$ lines contains a string of $k$ digits which are either $0$ or $1$. A $1$ in position $j$ means the character has the $j$’th feature, and a $0$ means that it does not have the $j$’th feature.
Output
Output a single line describing the features of Tira’s character in the same format as in the input. If there are multiple possible characters with the same smallest maximum similarity, any one of them will be accepted.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 5 01001 11100 10111 |
00010 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 4 0000 |
1111 |
