402575: GYM100812 B Set of Tasks

I was heading to the old tavern «ChivalryForces», because I knew that the Princess spent a lot of time there. In the basement of the tavern the bets on a popular joust «ACM ICPC» were taken. Disgusting place, full of all sorts of scum of society. On the tournament knights formed teams of three and performed tasks, which had been prepared earlier by the members of special jury consisting of n representatives of oligarchic clans and bandit gangs. The atmosphere was extremely tense there. The judges once nearly killed each other during the preparation of tasks.

They had prepared m tasks, but every judge had his own opinion which of them should have been included to the final set and which should have been kept for the next tournament. If the final set had included the task which the judge didn't want to see in it, or if it hadn't included the task he wanted to be included, he would have got terribly upset, and of course that upset included physical abuse with the use of bladed weapons. Little known that time bandit called Dragon was one of the judges, and he managed to correct everything. He suggested to choose such set of tasks for the tournament so that the number of judges who would become upset was as minimal as possible. Also, according to the rules, the number of tasks for the tournament had to be between eight and fifteen inclusively, and it should have been taken into account. It was not a great problem to choose such set of tasks. Much more difficult thing was to persuade those who got upset because of the fairness of that decision, but Dragon had a special approach to people.

The first line contains two integers separated by a space: n and m (1 ≤ n ≤ 5000, 8 ≤ m ≤ 5000) — the number of judges and the number of tasks correspondingly.

The next n lines contains m digits each, without spaces. The i-th line on its j-th position has digit 0 if the i-th judge doesn't want to see the j-th task in the final set, or digit 1 if he, on the contrary, wants this task to be included to the final set.

Output a line of m digits. On the j-th position output 0 if the j-th task should not be included to the final set, otherwise output 1 there. The number of ones in the line should be between 8 and 15, inclusively. If there are several suitable sets of tasks, output any of them.

4 20
11000000001111111111
11100000001111111111
11000000001111111111
10000000001111111111

11000000001111111111

8 20
10101010001111111111
10101001001111111111
10101010001111111111
10101001001111111111
11111001001111111111
11111001001111111111
11111001001111111111
11111001001111111111

10101001001111111111