The 2017 Nordic Collegiate Programming Contest

Start

2017-10-07 09:00 UTC

The 2017 Nordic Collegiate Programming Contest

End

2017-10-07 14:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -429 days 4:55:05

Time elapsed

5:00:00

Time remaining

0:00:00

Problem D
Distinctive Character

/problems/distinctivecharacter/file/statement/en/img-0001.jpg
Picture by Fairytalemaker on Pixabay
Tira would like to join a multiplayer game with $n$ other players. Each player has a character with some features. There are a total of $k$ features, and each character has some subset of them.

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