0042. HyperKitten

Input file name:	hyperkit.in
Output file name:	hyperkit.out
Time limit:	1 s
Memory limit:	64 megabytes

You are already familiar with the n-dimensional Kitten living on a surface of n-dimensional cube.

But somewhen he did not live there. He arrived there only twenty years ago (n-dimensional Kittens' life is very very long!) with m n-dimensional cows. Each cow selected one of the vertices where it found enough n-dimensional grass to graze.

And then the Kitten started to think – where it's better to build his n-dimensional house? He decided to build it in one of the vertices because the only roads those days passed via edges of the cube (the n-dimensional Kittens did not live there those days and did not build a n-dimensional town yet!). He decided to select a vertex minimizing (yeah, the Kittens are GREAT optimizers!) the total distance to all cows by edges.

So your task is to find such a vertex.

For this task you may assume that all edges of cube have length of 1. One of the vertices of the cube is (0, 0, …, 0), and all edges are parallel to coordinate axes. So any vertex of the cube may be coded by a sequence of n 0's and 1's.

Input file

The first line of the input file contains two integer numbers n and m (1≤ n≤ 200, 1≤ m≤ 300). Then m input lines follow with n symbols each. All of these symbols are 0's and 1's. The i-th symbol of j-th line represents the i-th coordinate of j-th cow.

Output file

Write to the output file exactly n symbols – the coordinates of the vertex nearest to cows.

The Kitten calculates the distance to cows separately from each other, so if there are two cows in one vertex, this distance will be calculated twice, etc.

If there are more than one answer, output any of them.

Examples:

hyperkit.in	hyperkit.out
2 2 00 11	10
2 3 00 11 11	11

Source: Petrozavodsk training camp, Summer 2002. Conclusive contest
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution