Exploding Kittens

Far far away, in an alien galaxy, M friends decide to meet up and play the "Exploding Kittens" game. They all agreed upon how to pick the meetup location: they will all show up at the house of the alien friend which lives closest to everyone else.

Their world is not like the 3D space we are used to, because it has N dimensions. They all live at integer coordinates in their world, meaning that a house location is an N-dimensional vector of the form (x1, x2, …, xn), where x1, x2, …, xn are all integers. At any time, an alien can move from one position to another only if exactly one of the vector's components changes by 1 unit in absolute value. For example, in a 2D space, from a given position he can only move to the North, West, South or East directions in one step.

Your task is to compute the minimal number of steps needed for all friends to get to the meeting point. This will be a SUM(di), where di represents the minimal number of steps needed for the i-th friend to arrive at the meeting place, starting from his house. In addition to this, you should print the number of friends whose houses satisfy this minimal distance requirement and their houses' coordinates, in lexicographical order.


The first line of input contains integers M and N, separated by a space.
Each of the following M lines contains N integers, representing the coordinates of a house.


The first line of the output should contain the minimum total meeting distance, as described in the statement.
The next line should contain the number of houses H for which the total meeting distance is minimal. The next H lines should contain the coordinates of these houses. The houses should be sorted lexicographically.


  • 1 ≤ M ≤ 50000
  • 1 ≤ N ≤ 25
  • 1 ≤ N * M ≤ 250000
  • 10-9 ≤ xij ≤ 109, where xij is the jth coordinate of the ith house


2 2
5 5
1 1
1 1
5 5

Sponsors Gold