Happy Birthday!!!
The cat Sonya's birthday is at the end of March. Just when all the cats and their girlfriends like to walk. Sonya has k friends, and they all want to congratulate her. To do this, Sonya decided to collect all of them in one place, then to go somewhere for a walk. Sonya loves her friends, therefore, she wants to choose a meeting place so that the sum of the distances traveled by her friends to this place, is minimal.
Since Sonya enjoys programming contests, she decided to do this task harder, making the space n-dimensional. Let the distance between the point (x_1, x_2, …, x_n) and the point (y_1, y_2, …, y_n) be the amount of (|x_1-y_1| + |x_2-y_2| + … |x_n-y_n|).
Input
In the first row you are given two numbers: k (1 ≤ k ≤ 150000) and n (1 ≤ n ≤ 10). Each of the next k lines contains n integers - the coordinates of the location of the current Sonya's friend. The absolute value of each coordinate do not exceed 50000.
Output
Print the coordinates of the optimal place for a meeting. Follow the format of the output shown in the example. If there are several such points, output the one with the less first coordinate. If the first coordinates are equal compare the second, and so on. Then, output a single number - the total distance traveled by Sonya's friends.