시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 512 MB127574857.831%

문제

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.

입력

The first line of input contains two integers n and k, where 1 ≤ n ≤ 105 is the number of players (excluding Tira) and 1 ≤ k ≤ 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 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.

예제 입력 1

3 5
01001
11100
10111

예제 출력 1

00010

예제 입력 2

1 4
0000

예제 출력 2

1111

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2017 D번

  • 문제를 만든 사람: Antti Laaksonen